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

0 条评论

• 2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)-G.Projection

Everybody knows that you are a TensorFlow fan. Therefore, you’ve been challenged...

• 并查集

POJ 的题真的是对小白选手的一个大的磨炼了，看了好久才明白题意，然后发现还是不会写题意就是给你一个数n，然后又n次操作，每次操作有两种情况如果第一个字符是 M...

• POJ-2585-Window Pains

Window PainsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 2915 ...

1006. Sign In and Sign Out (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 1600...

• 《权力的游戏》最终季上线！谁是你最喜爱的演员？这里有一份Python教程 | 附源码

《权力的游戏》最终季已于近日开播，对于全世界翘首以待的粉丝们来说，其最大的魅力就在于“无法预知的人物命运”。那些在魔幻时代的洪流中不断沉浮的人们，将会迎来怎样的...

• 10分钟上手，OpenCV自然场景文本检测（Python代码+实现）

EAST文本检测器需要OpenCV3.4.2或更高版本，有需要的读者可以先安装OpenCV。

• 目标检测一波接着一波 | YOLOv5又悄悄来袭！（附源码论文链接）

期待已久的检测经典又来来了一波强袭——yolov5。其实yolov5没有完整的文件，现在最重要的应该是把yolov4弄清楚，在目标检测领域中受益匪浅，可以在某些...

• 10分钟上手，OpenCV自然场景文本检测（Python代码+实现）

EAST文本检测器需要OpenCV3.4.2或更高版本，有需要的读者可以先安装OpenCV。

The Head Elder of the tropical island of Lagrishan has a problem. A burst of ...

• HDU 1866 A + B forever!

A + B forever! Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/3...