本文主要是介绍Ural 1303. Minimal Coverage / 最小区间覆盖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
求最小区间覆盖0-m 以前做过 现在墨迹半天写出来 弱爆了
像这样的1 9 和 2 7 根据贪心原理后者不需要直接去掉
然后按照起点从小到大排序 在按照终点从大到小排序 贪心模拟一下每次能不选就不选
(1 6) (1 5) (2 9) (3 10) (7 10)选择(1 6) 之后 下一个选择是(3 10) 他是最后一个能选的 不选就会断开 并且比选(2 9)更优
会不会说如果是这样(1 6) (1 5) (2 12) (3 10) (7 10) 不选(3 10) 选（2 12）更优 之前说过了 预处理(2 10)包含了(3 10) 所以(3 10) 在贪心之前先去掉了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 100010;
struct node
{int s, e;
}a[maxn], b[maxn], ans[maxn];
bool cmp(node a, node b)
{if(a.s != b.s)return a.s < b.s;return a.e > b.e;
}
int main()
{int m, n;while(scanf("%d", &m) != EOF){n = 0;int s, e;while(scanf("%d %d", &s, &e) , s || e){a[n].s = s;a[n++].e = e;}sort(a, a+n, cmp);int i, j, k = 0;b[0] = a[0];for(i = 1; i < n; i++){if(a[i].s > b[k].s && a[i].e > b[k].e)b[++k] = a[i];}n = k;n++;b[n].s = m+1;b[n].e = m+1;k = 0;int y = -1;for(i = 0; i < n; i++){if(b[i+1].s > 0 && b[i].s <= 0){ans[k++] = b[i];y = b[i].e;break;}}if(!k){puts("No solution");continue;}for(; i < n; i++){if(y >= m){break;}if(b[i+1].s > y && b[i].s <= y){ans[k++] = b[i];y = b[i].e;}}if(!k || y < m){puts("No solution");continue;}else{printf("%d\n", k);for(i = 0; i < k; i++){printf("%d %d\n", ans[i].s, ans[i].e);}}}return 0;
}
/*
1
0 100
-1 0
-5 -3
2 5
0 04
0 2
3 4
-1 0
-5 -3
3 5
0 06
0 2
1 2
2 3
3 4
4 5
2 4
5 6
3 6
0 9
-1 100
0 0*/
这篇关于Ural 1303. Minimal Coverage / 最小区间覆盖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
