网站开发与软件开发区别,百度推广培训机构,卖备案域名被抓,专业app开发定制公司用i来表示x坐标轴上坐标为[i-1#xff0c;i]的长度为1的区间#xff0c;并给出n#xff08;1≤n≤200#xff09;个不同的整数#xff0c;表示n个这样的区间。 现在要求画m条线段覆盖住所有的区间#xff0c;条件是#xff1a;每条线段可以任意长#xff0c;但是要求所… 用i来表示x坐标轴上坐标为[i-1i]的长度为1的区间并给出n1≤n≤200个不同的整数表示n个这样的区间。 现在要求画m条线段覆盖住所有的区间 条件是每条线段可以任意长但是要求所画线段的长度之和最小 并且线段的数目不超过m(1≤m≤50。 Input 输入包括多组数据每组数据的第一行表示点n和所需线段数m后面的n行表示点的坐标Output 输出每组输出占一行表示线段的长度。Example Input 5 3
1 3 8 5 11 Example Output 7 #include stdio.h #include stdlib.h void q(int d[],int n)//降序排序 { int i,j,t; for(i0;in-1;i) for(j0;jn-1-i;j) if(d[j]d[j1]) { td[j]; d[j]d[j1]; d[j1]t; } } int main() { int m,n,i; int p[201]; int d[201]; while(~scanf(%d%d,n,m)) { for(i0;in;i) { scanf(%d,p[i]); } q(p,n);//降序排列 for(i0;in-1;i) d[i]p[i]-p[i1]-1;//相邻两段间的距离 q(d,n-1);//距离之间降序 if(mn) printf(%d\n,n); else { int nline1;//线段的个数 int t1p[0]-p[n-1]1;//最长距离 int devide0; while((nlinem)(d[devide]0)) { nline; t1t1-d[devide];//距离减小最长的一段 devide; } printf(%d\n,t1); } } return 0; }
