Minimal coverage (貪心，最小覆蓋)

題目大意：先確定一個M，然后輸入多組線段的左端和右端的端點坐標，然后讓你求出來在所給的線段中能夠

把[0, M]?區域完全覆蓋完的最少需要的線段數，并輸出這些線段的左右端點坐標。

思路分析：

? ? ? ?線段區間的起點是0，那么找出所有區間起點小于0中的最合適的區間。

? ? ? ?因為需要盡量少的區間，所以選擇右端點更大的區間，它包含所選線段更大。

? ? ? ?如果在所有區間中找到了解，且右端點小于M，則把找到的區間的右端點定為新的線段區間的起點。

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 
 7 
 8 using namespace std;
 9 
10 struct node
11 {
12     int L, R;
13 }a[100010], b[100010];
14 
15 bool cmp(node a, node b)
16 {
17     return a.R > b.R;
18 }
19 
20 int main() 
21 {
22     int M;
23     while(scanf("%d", &M) != EOF)
24     {
25         int Index = 0;
26         while(1)
27         {
28             scanf("%d%d", &a[Index].L, &a[Index].R);
29             if(a[Index].L == 0 && a[Index].R == 0)
30                 break;
31             ++Index;
32         }
33         
34         sort(a, a+Index, cmp);
35         
36         int border = 0;        // 起始邊界點為0 
37         int cnt = 0;
38         while(border < M)
39         {
40             int i = 0;
41             for(; i < Index; ++i)
42             {
43                 // a[i].R >= border提交將會Runtime error 
44                 if(a[i].L <= border && a[i].R > border)
45                 {
46                     b[cnt] = a[i];
47                     cnt++;
48                     border = a[i].R;    // 更新邊界點 
49                     break;
50                 }
51             }
52             if(i == Index)
53                 break;
54         }
55         
56         
57         if(border < M)
58             cout << "No solution" << endl;
59         else
60         {
61             cout << cnt << endl;
62             for(int i = 0; i < cnt; ++i)
63                 cout << b[i].L << " " << b[i].R << endl;
64         }
65     }
66             
67     return 0;
68 }

轉載于:https://www.cnblogs.com/FengZeng666/p/11120095.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/247661.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/247661.shtml
英文地址，請注明出處：http://en.pswp.cn/news/247661.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！