网站建设使用情况网站内容建设

Description

临近期末考试，自习室的学生来来往往。

这可忙坏了管理自习室的大爷，他随时准备开关灯。

自习室只要有学生来，就需要开灯。一开始没有学生来之前灯是关闭的。

周日这一天共有 n 位同学来自习，第 i 个同学将在时间 Ti​ 来自习室，并在时间 Ti​+1 离开。

按照规定任何时间最多一个同学在自习室（防止同学之间说话影响学习）。

大爷可以随时开灯和关灯（有学生在自习室的时候不能关灯）。

由于学生频繁出入，大爷已经厌倦了每天反复开关灯，所以他决定一天最多开灯 k 次，当然他想尽量减少灯亮的时间（节约用电）。

请计算这一天灯亮时间的最小值。

Input

第一行包含两个空格分隔的整数 n，k。

接下来 n 行,第 i 行包含整数 Ti​，表示第 i 个学生将在时间 Ti​ 到达自习室，并在时间 Ti​+1 离开自习室。

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-2）+（9-8）=4.

数据规模与约定

所有 的数据，1≤n≤105，1≤k≤n，1≤Ti​≤109（1≤i≤n）,Ti​<Ti+1​（1≤i≤n−1）。

对于20 的数据：n≤20。

对于30% 的数据：n≤5000。

对于50% 的数据：没有额外的限制。

 AC（100pts）:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main(){int n,k;cin>>n>>k;int a[n],sum=n,kk[n-1];for(int i=0;i<n;i++){cin>>a[i];if(i!=0){kk[i-1]=a[i]-a[i-1]-1;}}sort(kk,kk+n-1);for(int i=0;i<n-k;i++){sum+=kk[i];}cout<<sum;return 0;
}