題目描述 用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; }
