區間覆蓋問題

2019-11-11 03:25:24

字體：大中小

來源：轉載

供稿：網友

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 31 3 8 5 11Example Output
7Hint
 Author
用一條線段的長度減去間隔最大的m-1組間隔， 得到的就是最短長度01 #include<stdio.h>
02 struct dog
03 {
04     int c;
05     int b;
06 } a[201], t;
07 int main()
08 {
09     int n, m, i, l, l2, s, j;
10     while(scanf("%d%d", &n, &m) != EOF)
11     {
12         l = 0;
13         for(i = 0; i < n; i++)
14         {
15             scanf("%d", &a[i].c);
16         }
17         for(i = 0; i < n - 1; i++)
18         {
19             for(j = i + 1; j < n; j++)
20             {
21                 if(a[i].c > a[j].c)
22                 {
23                     t = a[i];
24                     a[i] = a[j];
25                     a[j] = t;
26                 }
27             }
28         }
29         for(j = 0,i = 1; i < n; i++, j++)
30         {
31             a[j].b = a[i].c - 1 - a[i-1].c;
32         }
33         for(i = 0; i < n - 1; i++)
34         {
35             for(j = i + 1; j < n; j++)
36             {
37                 if(a[i].b < a[j].b)
38                 {
39                     s = a[i].b;
40                     a[i].b = a[j].b;
41                     a[j].b = s;
42                 }
43             }
44         }
45         for(i = 0; i < m - 1; i++)
46         {
47             l += a[i].b;
48         }
49         l2 = a[n-1].c - a[0].c + 1 - l;
50         printf("%d/n", l2);
51     }
52     return 0;
53 }