手机网站建设经验,代理网络软件,做网站开发要装什么软件,八上数学优化设计答案Description
临近期末考试#xff0c;自习室的学生来来往往。
这可忙坏了管理自习室的大爷#xff0c;他随时准备开关灯。
自习室只要有学生来#xff0c;就需要开灯。一开始没有学生来之前灯是关闭的。
周日这一天共有 n 位同学来自习#xff0c;第 i 个同学将在时间 …Description
临近期末考试自习室的学生来来往往。
这可忙坏了管理自习室的大爷他随时准备开关灯。
自习室只要有学生来就需要开灯。一开始没有学生来之前灯是关闭的。
周日这一天共有 n 位同学来自习第 i 个同学将在时间 Ti 来自习室并在时间 Ti1 离开。
按照规定任何时间最多一个同学在自习室防止同学之间说话影响学习。
大爷可以随时开灯和关灯有学生在自习室的时候不能关灯。
由于学生频繁出入大爷已经厌倦了每天反复开关灯所以他决定一天最多开灯 k 次当然他想尽量减少灯亮的时间节约用电。
请计算这一天灯亮时间的最小值。
Input
第一行包含两个空格分隔的整数 nk。
接下来 n 行,第 i 行包含整数 Ti表示第 i 个学生将在时间 Ti 到达自习室并在时间 Ti1 离开自习室。
Output
一行包含一个整数为灯亮时间的最小值。
Sample Input 1
3 2
2
4
8
Sample Output 1
4
Sample Input 2
3 1
2
4
6
Sample Output 2
5
Sample Input 3
3 3
1
3
6
Sample Output 3
3
Sample Input 4
10 5
1
2
5
6
8
11
13
15
16
20
Sample Output 4
12
Hint
样例1说明
第1个同学来时第2时刻开灯
第2位同学离开时第5时刻关灯
第3位同学来时第8时刻开灯
第3位同学离开时第9时刻关灯。
灯亮的时间是5-29-84.
数据规模与约定
所有 的数据1≤n≤1051≤k≤n1≤Ti≤1091≤i≤n,TiTi11≤i≤n−1。
对于20 的数据n≤20。
对于30% 的数据n≤5000。
对于50% 的数据没有额外的限制。 AC100pts:
#includeiostream
#includebits/stdc.h
using namespace std;
int main(){int n,k;cinnk;int a[n],sumn,kk[n-1];for(int i0;in;i){cina[i];if(i!0){kk[i-1]a[i]-a[i-1]-1;}}sort(kk,kkn-1);for(int i0;in-k;i){sumkk[i];}coutsum;return 0;
}
