问题描述
用?i?来表示?x?坐标轴上坐标为 (i?1,i)、长度为?1?的区间，并给出 n(1≤n≤200)?个不同的整数，表示?n?个这样的区间。现在要求画?m?条线段覆盖住所有的区间，条件是每条线段可以任意长，但是要求所画线段的长度之和最小，并且线段的数目不超过 m(l≤m≤50)。
Tip: 本题为单组输入
输入描述
第 1 行表示区间个数?nn?和所需线段数?mm, 第 2 行表示?n?个点的坐标。
输出描述
一行，输出?m?条线段的最小长度和。
样例输入
Copy to Clipboard5 3 1 3 8 5 11 样例输出
Copy to Clipboard7/*
* @Description: To iterate is human, to recurse divine.
* @Autor: Recursion
* @Date: 2022-04-25 14:57:38
* @LastEditTime: 2022-04-25 15:33:07
*/
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int INF = 1e9 + 10;
const int N = 500;
int n,m;
int a[N];
int dis[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= n;i ++)
cin >> a[i];
sort(a + 1, a + 1 + n);
if(n <= m){
cout << n << endl;
return 0;
}
for(int i = 1;i <= n - 1;i ++){
dis[i] = a[i + 1] - a[i] - 1;
}
sort(dis + 1, dis + n,greater<int>());
int ans = a[n] - a[1] + 1;
int num = 1;
while(num < m){
ans -= dis[num];
num ++;
}
cout << ans << endl;
return 0;
}
