区间覆盖问题

Problem Description

 用i来表示x坐标轴上坐标为[i-1，i]的长度为1的区间，并给出n（1≤n≤200）个不同的整数，表示n个这样的区间。

现在要求画m条线段覆盖住所有的区间，

条件是：每条线段可以任意长，但是要求所画线段的长度之和最小，

并且线段的数目不超过m(1≤m≤50）。

 

Input

 输入包括多组数据，每组数据的第一行表示区间个数n和所需线段数m，第二行表示n个点的坐标。

Output

 每组输出占一行，输出m条线段的最小长度和。

Example Input

5 3 1 3 8 5 11

Example Output

7 代码如下 #include<stdio.h> #define N 230 void sort(int value[],int n) {     int i,j ,t;     for(i = 0;i<n;i++)     {         for(j = 0;j<n-1-i;j++)         {             if(value[j]<value[j+1])             {                 t = value[j];                 value[j] = value[j+1];                 value[j+1] = t;             }         }     } } int main() {     int n ,m ,i;     int nline ,devide,totall;     int position[N];//保存区间数     int distance [N-1];//区间间隔     while(scanf("%d %d",&n,&m)!=EOF)     {         for(i = 0;i<n;i++)         scanf("%d",&position[i]);         sort(position,n);//将区间逆序排序         for(i = 0;i<n-1;i++)         distance[i] = position[i]-position[i+1]-1;//求区间间隔         sort(distance,n-1);//区间间隔逆序排序         //两种情况        if(n<=m)        printf("%d\n",n);        else        {            nline = 1;//假设区间被一整条直线覆盖然后再自选区间隔中最大的一一删除            totall = position[0]-position[n-1]+1;//总区间长度            devide = 0;//间隔下标的表示            while(nline <m&&distance[devide]>0)//总条数要小于直线数   而且间隔元素不能为零 间隔为零就不需要去掉了           {              nline++;              totall -=distance[devide];             devide++;           }           printf("%d\n",totall);        }     }     return 0; }