点击获取原题链接
区间覆盖问题 Time Limit: 1000MS Memory Limit: 65536KB Problem Description 用i来表示x坐标轴上坐标为[i-1，i]的长度为1的区间，并给出n（1≤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 Hint Author贪心策略：
#include <bits/stdc++.h> using namespace std; int cmd(int a,int b)///升序 { return a>b; } int main() { int m,n; int a[200+10]; while(cin>>n>>m) { for(int i=0; i<n; i++) { cin>>a[i]; } sort(a,a+n);///按升序排好数据 int max=a[n-1]-a[0]+1;///总共的线段长 int b[200+10];///线段的差值 for(int i=0; i<n-1; i++) { b[i]=a[i+1]-a[i]-1; } sort(b,b+n-1,cmd); if(n <= m)/// 要填充的 线段数大于 区间数 { cout<<n<<endl; } else { int count=1;///线段数 开始时为1 即覆盖全部的区间 while(1) { if(count < m)///线段数还没 到最大值 开一个新选段 { max-=b[0];///减去两个线段中间的 间隔 count++; } else break; /// 选段数到达 最大值退出贪心 b[0]=0;/// 该间隔 为空 sort(b,b+n-1,cmd);/// 再次排序 } cout <<max<<endl; } } return 0; }