欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

缺席的神官

程序员文章站 2022-06-19 09:26:17
...

缺席的神官


广东工业大学2019年新生赛
题目描述面前的巨汉,让我想起了多年前的那次,但这个巨汉身上散布着让人畏惧害怕的黑雾。即使

看不到脸,但是威严却在这个从者身边不断围绕。

「吾乃七骑之中的骑士(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。

输出
输出懒惰的祭司进行工作的最少天数

样例输入

4 100 2
20 30 75 80

样例输出

17

提示样例的

2段为[20,30],[75,80],进行工作的最少天数为:11+6=17

思路:
先把所给数组的间隔存入一个新数组,然后从小到大排序,遍历该数组到 1 ~ x-k+1,累加起来组后再加上 k 即可。

源代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int a[N],b[N],n,m,k,sum=0;
int main() {
 cin>>n>>m>>k;
 for(int i=1; i<=n; i++) cin>>a[i];
 for(int i=1; i<=n; i++) b[i]=a[i+1]-a[i];
 sort(b+1,b+n);
 for(int i=1; i<=n-k; i++) sum+=b[i];
 sum+=k;
 cout<<sum<<endl;
 return 0;
}

AC


祝各位备战期末考的学生取得满意的成绩!!!
缺席的神官