首页 > 代码库 > UVa 10020 (最小区间覆盖) Minimal coverage
UVa 10020 (最小区间覆盖) Minimal coverage
题意：
数轴上有n个闭区间[ai, bi]，选择尽量少的区间覆盖一条指定线段[0, m]
算法：
[start, end]为已经覆盖到的区间
这是一道贪心
把各个区间先按照左端点从小到大排序，更新start为end，如果区间1在start的右端，则无解，因为其他区间更不可能覆盖到
然后在剩下的能覆盖到start的区间里面选择能覆盖到最右端的区间并更新end，然后记录在path里面。如果end的已经将m覆盖则退出循环
如果遍历完所有的区间后end依然没能覆盖到start，则无解
最后按照parh里面记录的路径输出区间即可
1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 100000 + 10; 9 10 struct Range11 {12 int a, b;13 inline bool operator< (const Range& rhs) const14 {15 return a < rhs.a || (a == rhs.a && b < rhs.b);16 }17 }ranges[maxn];18 int path[maxn];19 20 int main(void)21 {22 #ifdef LOCAL23 freopen("10020in.txt", "r", stdin);24 #endif25 26 int T;27 scanf("%d", &T);28 while(T--)29 {30 int a, b, m, n = 0;31 scanf("%d", &m);32 while(scanf("%d%d", &a, &b) == 2)33 {34 if(a == 0 && b == 0) break;35 if(a > m) continue;36 if(a < 0) a = 0;37 ranges[n].a = a;38 ranges[n++].b = b;39 }40 sort(ranges, ranges + n);41 int minCover = 0;42 int start = 0, end = 0;43 for(int i = 0; i < n; )44 {45 start = end;46 if(ranges[i].a > start)47 break;48 while(i < n && ranges[i].a <= start)49 {50 if(ranges[i].b > end)51 {52 end = ranges[i].b;53 path[minCover] = i;54 }55 ++i;56 }57 ++minCover;58 if(end >= m) break;59 }60 if(end < m) minCover = 0;61 printf("%d\n", minCover);62 for(int i = 0; i < minCover; ++i)63 printf("%d %d\n", ranges[path[i]].a, ranges[path[i]].b);64 if(T)65 printf("\n");66 }67 return 0;68 }
UVa 10020 (最小区间覆盖) Minimal coverage
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。