题目描述
用i来表示x坐标轴上坐标为[i-1,i]的长度为1的区间,并给出n(1≤M≤200)个不同的整数,表示n个这样的区间。
现在要求画m条线段覆盖住所有的区间,
条件是:每条线段可以任意长,但是要求所画线段的长度之和最小,
并且线段的数目不超过N(1≤N≤50)。
输入
输入包括多组数据,每组数据的第一行表示点n,和所需线段数m,后面的n行表示点的坐标
输出
输出每组输出占一行表示线段的长度。
示例输入
5 3 1 3 5 8 11
示例输出
7
提示
来源
示例程序
思路: 先把总的线的长度求出来 即从第一个线段的起点到最后一个线段的终点的长度sum, 然后求出每2个区间之间的距离a[i]
之后用sum减去m-1个最大的a[i] 相当于把整条线分成了m份
#include<stdio.h> #include<algorithm> using namespace std; int main() { int val[300],i, n, m, sum, dis[300]; while(~scanf("%d %d", &n, &m)) { for(i = 0; i < n; i++) scanf("%d",&val[i]); std::sort(val, val+n); for(i = 0; i < n - 1; i++) dis[i] = val[i+1] - val[i] - 1; std::sort(dis, dis+n-1); sum = val[n-1] - val[0] + 1; int j = n - 2; for(i = 1; i < m && i < n; i++) sum -= dis[j--]; printf("%d\n",sum); } return 0; }