专栏首页一Wa哇一天CF-1197C-C. Array Splitting

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

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 ...

    某些人
  • PAT 1006 Sign In and Sign Out

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

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

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

    AI科技大本营
  • 10分钟上手,OpenCV自然场景文本检测(Python代码+实现)

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

    新智元
  • 目标检测一波接着一波 | YOLOv5又悄悄来袭!(附源码论文链接)

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

    计算机视觉研究院
  • 10分钟上手,OpenCV自然场景文本检测(Python代码+实现)

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

    磐创AI
  • 九度OJ——1154Jungle Roads

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

    AI那点小事
  • HDU 1866 A + B forever!

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

    ShenduCC

扫码关注云+社区

领取腾讯云代金券