2019年广东工业大学腾讯杯新生程序设计竞赛（同步赛）E-缺席的神官

链接：https://ac.nowcoder.com/acm/contest/3036/E 来源：牛客网 题目描述 面前的巨汉，让我想起了多年前的那次，但这个巨汉身上散布着让人畏惧害怕的黑雾。即使看不到脸，但是威严却在这个从者身边不断围绕。 「吾乃七骑之中的骑士(rider)，你们就是御主所说的阻扰者吧」 「是」我从雪茄盒里面掏出一根雪茄，想稍微冷静一下。 「那便无需多言了」和我签订了暂时契约的理查一世倒是直接拔剑了，如此看来查理一世的职介就是剑士(saber)。 「我看你的御主倒是没有这个想法吧」 他似乎看出了我的想法，虽然只是亡魂的影子，但也曾是人，能洞察人心。 「您是这样的想法吗」理查一世把剑收了起来。 「是啊，虽然参与圣杯战争的御主和从者目的是实现愿望，但既然是残缺的圣杯，我也会猜想是否从者对圣杯的渴望并没有那么高，是否有值得交涉的余地」 「哈」巨汉笑了，「真是大胆的妄想啊，但你应该明白圣杯显现的方法吧，所以这一切都是不可避免的。但我也不想使用武力，解答我的困惑吧，魔术师，如果你们能回答出来，我就会放弃」 「我明白了，洗耳恭听」 「古时有一个懒惰的祭司，而祭司在连续m天内必须一直去神庙内工作，但祭司的怠惰在诱惑着祭司，于是祭司决定这段时间内只选出k个连续的时间段去神庙工作，但是高级祭司(祭司的上级)又会定期对神庙内的工作人员进行点名。祭司不想因此失去这份工作，所以提前知道了高级祭司会点名n次以及每次点名的日子。所以祭司把点名的日子纳入工作的日子当中的同时又尽可能的偷懒。那么，这个祭司到底工作了多少天呢」 「这个答案很简单，荷鲁斯」 输入描述: 第一行输入三个整数n,m,k (1 <= n <= 2000) (n <= m <= 109) (1<= k <= n)，分别为高级祭司的点名次数,原本需要工作的天数和懒惰的祭司的工作次数。

第二行输入n个数字ai (1 <= ai <= m),为高级祭司检查的日期。 输入保证对于任意的i,j (1<= i<j <= n)，都有ai < aj。

输出描述: 输出懒惰的祭司进行工作的最少天数 示例1 输入 复制 4 100 2 20 30 75 80 输出 复制 17 说明 样例的2段为[20,30],[75,80]，进行工作的最少天数为：11+6=17

#include<iostream>
#include<algorithm>
#include<vector>
using namespace  std;
int a[100000];
struct Node{
    int x,y,val;
} ans[100000];
int flag[100000];
bool cmp(Node a,Node b)
{
    return a.val<b.val;
}
int main()
{
    int N,maxi,k;
    cin>>N>>maxi>>k;
    for(int i=0;i<N;i++)
    {
        cin>>a[i];
        i==0? i=0: ans[i].val=a[i]-a[i-1],ans[i].x=i-1, ans[i].y=i;
    }
    sort(ans,ans+N,cmp);
    int cnt=k;
    for(int i=1;i<N-k+1;i++)
    {
        cnt+=ans[i].val;
        flag[ans[i].x]++;
        flag[ans[i].y]++;
    }
    cout<<cnt<<endl;
    return 0;
}