贪心 URAL 1303 Minimal Coverage

 1 /*
 2     题意：最少需要多少条线段能覆盖[0, m]的长度
 3     贪心：首先忽略被其他线段完全覆盖的线段，因为选取更长的更优
 4             接着就是从p=0开始，以p点为标志，选取 (node[i].l <= p && p < node[i+1].l)
 5     详细解释：http://www.cnblogs.com/freezhan/p/3219046.html
 6 */
 7 #include <cstdio>
 8 #include <iostream>
 9 #include <algorithm>
10 #include <cstring>
11 #include <cmath>
12 using namespace std;
13 
14 const int MAXN = 1e6 + 10;
15 const int INF = 0x3f3f3f3f;
16 struct Node
17 {
18     int l, r;
19 }node[MAXN], ans[MAXN];
20 
21 bool cmp(Node x, Node y)
22 {
23     if (x.l == y.l)    return x.r > y.r;
24     else    return x.l < y.l;
25 }
26 
27 int main(void)        //URAL 1303 Minimal Coverage
28 {
29     //freopen ("R.in", "r", stdin);
30 
31     int m;
32     while (scanf ("%d", &m) == 1)
33     {
34         int n = 0;    int u, v;
35         while (scanf ("%d%d", &u, &v) == 2 && (u || v))
36             node[++n].l = u, node[n].r = v;
37         sort (node+1, node+1+n, cmp);
38 
39         int k = 1;
40         for (int i=2; i<=n; ++i)        //cover
41         {
42             if (node[k].l < node[i].l && node[k].r < node[i].r)
43             {
44                 node[++k] = node[i];
45             }
46         }
47 
48         n = k;    int p = 0;    int cnt = 0;
49         node[n+1].l = node[n+1].r = m + 1;
50         for (int i=1; i<=n; ++i)
51         {
52             if (node[i].l <= p && p < node[i+1].l)
53             {
54                 ans[++cnt] = node[i];    p = node[i].r;
55             }
56             if (p >= m)
57             {
58                 printf ("%d
", cnt);
59                 for (int i=1; i<=cnt; ++i)
60                 {
61                     printf ("%d %d
", ans[i].l, ans[i].r);
62                 }
63                 break;
64             }
65         }
66 
67         if (p < m)    puts ("No solution");
68     }
69 
70     return 0;
71 }
72 
73 /*
74 No solution
75 */
编译人生，运行世界！