用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

#include <stdio.h>
#include <stdlib.h>
void q(int d[],int n)//降序排序；
{
? ? int i,j,t;
? ? for(i=0;i<n-1;i++)
? ? ? ? for(j=0;j<n-1-i;j++)
? ? ? ? if(d[j]<d[j+1])
? ? {
? ? ? ? t=d[j];
? ? ? ? d[j]=d[j+1];
? ? ? ? d[j+1]=t;
? ? }
}
int main()
{
? ? int m,n,i;
? ? int p[201];
? ? int d[201];
? ? while(~scanf("%d%d",&n,&m))
? ? {
? ? ? ? for(i=0;i<n;i++)
? ? ? ? {
? ? ? ? ? ? scanf("%d",&p[i]);
? ? ? ? }
? ? ? ? q(p,n);//降序排列；
? ? ? ? for(i=0;i<n-1;i++)
? ? ? ? ? ? d[i]=p[i]-p[i+1]-1;//相鄰兩段間的距離；
? ? ? ? q(d,n-1);//距離之間降序；
? ? ? ? if(m>=n)
? ? ? ? ? ? printf("%d\n",n);
? ? ? ? else
? ? ? ? {
? ? ? ? ? ? int nline=1;//線段的個數；
? ? ? ? ? ? int t1=p[0]-p[n-1]+1;//最長距離；
? ? ? ? ? ? int devide=0;
? ? ? ? ? ? while((nline<m)&&(d[devide]>0))
? ? ? ? ? ? {
? ? ? ? ? ? ? ? nline++;
? ? ? ? ? ? ? ? t1=t1-d[devide];//距離減小最長的一段；
? ? ? ? ? ? ? ? devide++;
? ? ? ? ? ? }
? ? ? ? ? ? printf("%d\n",t1);
? ? ? ? }
? ? }
? ? return 0;
}

總結

以上是生活随笔為你收集整理的区间覆盖问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。