区间覆盖问题

PRoblem Description

Input

Output

Example Input

5 31 3 8 5 11
Example Output
7
Hint
 
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
}