CF1197C 【Array Splitting】Editional

CF1197C 【Array Splitting】

You are given a sorted array a1,a2,…,an (for each index i>1 condition ai≥ai−1 holds) and an integer k.
You are asked to divide this array into k non-empty consecutive subarrays. Every element in the array should be included in exactly one subarray.
Let max(i) be equal to the maximum in the i-th subarray, and min(i)min(i) be equal to the minimum in the ii-th subarray. The cost of division is equal to ∑i=1k(max(i)−min(i)). For example, if a=[2,4,5,5,8,11,19] and we divide it into 3 subarrays in the following way: [2,4],[5,5],[8,11,19], then the cost of division is equal to (4−2)+(5−5)+(19−8)=13.
Calculate the minimum cost you can obtain by dividing the array aa into kk non-empty consecutive subarrays.

Input
The first line contains two integers nn and kk (1≤k≤n≤3⋅10^5).
The second line contains nn integers a1,a2,…,an(1≤ai≤10^9, ai≥ai−1).

Output
Print the minimum cost you can obtain by dividing the array aa into kk nonempty consecutive subarrays.

Examples
input
6 3
4 8 15 16 23 42
output
12
input
4 4
1 3 3 7
output
0
input
8 1
1 1 2 3 5 8 13 21
output
20
Note
In the first test we can divide array a in the following way: [4,8,15,16],[23],[42].

题解：
差分+贪心
我们将这个问题转化为把一个排好序的数组（存储原数组两两元素的差）分割k-1次。
贪心，将差数组各个元素之和减去前k-1打的元素即是答案。
代码：

#include <bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for (ll i=x;i<=y;i++)
typedef long long ll;
int main()
{
    int n,k;
    cin>>n>>k;
    int a[n+1],cha[n+1];
    rep(i,1,n)
    {
        cin>>a[i];
    }
    cha[1]=0;
    rep(i,2,n)
    {
        cha[i]=a[i]-a[i-1];//存储两两元素的差
    }
    sort(cha+1,cha+n+1);
    int ans;
    ans=0;
    rep(i,1,n-k+1)
    {
        ans+=cha[i];//前n-k+1小的数之和就是答案
    }
    cout<<ans<<endl;
    return 0;
}