CF1197C

题意：

有一个递增的数列，把它分成k段，找到这样的分段方法，即每段最大值减最小值的和最小

解法：

分成k段，即要加k-1个隔断，这k-1个隔断，能隔开差值最大的几个，那最后得到分隔后的各段最大最小差值和最小

CODE:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

#define LL long long

const int N = 3e5 + 100;

int n,a[N],k;

vector<int> G;

int main() {

	scanf("%d%d",&n,&k);

	for(int i = 1 ; i <= n ; ++i)

		scanf("%d",&a[i]);

	for(int i = 2 ; i <= n ; ++i)

        G.push_back(a[i - 1] - a[i]);

	sort(G.begin(), G.end());

	int ans = a[n] - a[1];

	for(int i = 0 ; i < k - 1 ; ++i) ans += G[i];

	printf("%d",ans);

    //system("pause");

 	return 0;

}

巴特西

CF1197C

CF1197C

题意：

解法：

CODE:

最新文章

热门文章