CF-1197C-C. Array Splitting

CF-1197C-C. Array Splitting

C. Array Splitting time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output

      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) be equal to the minimum in the i-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 a into k non-empty consecutive subarrays.

Input The first line contains two integers n and k (1≤k≤n≤3⋅105). The second line contains n integers a1,a2,…,an (1≤ai≤109, ai≥ai−1).

Output Print the minimum cost you can obtain by dividing the array a into k 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]. 题目传送门   刚开始这一题我一时不会写有点思路但是就是写不出来好难受呀！后来还是问我师傅了！ 结果发现还是一个贪心，因为他需要最小值所以每次先把距离最大的删除那么结果不就是最小了，先依次作差，然后sort排序从大到小依次减去k-1个数就行！剩下的就是答案了

#include<iostream>
#include<algorithm>
using namespace std;

int a[300300];
int b[300300];
int main()
{
    ios::sync_with_stdio(false);
    int n,m;
    while(cin>>n>>m)
    {
        cin>>a[0];
        int sum=0;
        for(int i=1;i<n;i++)
        {
            cin>>a[i];
            b[i-1]=a[i]-a[i-1];//用数组B存差值； 
            sum+=b[i-1];       //先求差值之和最后再减； 
        }
        sort(b,b+n-1,greater<int>());//从大到小排序 
        for(int i=0;i<m-1;i++)//从大到小开始删除 
        {
            sum-=b[i];
        }
        cout<<sum<<endl; //输出剩余的结果 
    }
    return 0;
}