山东理工大学OJ 2074 区间覆盖问题


		题目描述
 用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份
[cpp] 
#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;  
}

补充：软件开发 , C++ ,