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;
}

 上一篇
树的直径 树的直径
我真的是好惨一男的呀!今天又被吊打一天好不容易搞懂树的直径了,又遇见树形dp!好惨呀!还有dfs!希望到时候有一个大佬可以带我飞!!!
2019-07-25
下一篇 
HPU第一次积分赛 E.Max Gcd HPU第一次积分赛 E.Max Gcd
E. Max Gcd 单点时限: 2.0 sec内存限制: 512 MB 一个数组a,现在你需要删除某一项使得它们的gcd最大,求出这个最大值。 输入格式第一行输入一个正整数n,表示数组的大小,接下来一行n个数,第i个数为ai。(
2019-07-22
  目录