题目链接:http://codeforces.com/contest/1197/problem/C
题意:
给出一个有序数组,划分成n个子数组。求出每个子数组中最大值与最小值之差。然后求出所有差的和,问如何划分使得这个和最小。
分析:
求出这个数组对应的差分数组。对这个差分数组求和,最大的k-1个数不要加。
为什么会这样,举个例子。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 300010;
LL a[N];
LL b[N];
int main()
{
int n, k;
while(scanf("%d %d", &n, &k) != EOF)
{
for(int i=0; i<n; i++)
scanf("%lld", &a[i]);
b[0] = 0;
for(int i=1; i<n; i++)
{
b[i] = a[i] - a[i-1];
}
sort(b, b+n);
LL sum = 0;
for(int i=0; i<n-k+1; i++)
{
sum += b[i];
}
printf("%lld\n", sum);
}
return 0;
}