UVA 10020 Minimal coverage 区间覆盖问题 贪心
题意：给出M，以及多个区间，求能覆盖[0,M]的最少的区间。
小白上以及给出了很好的思路了。但是实现起来卡了卡了好久，果然若菜编码能力是硬伤啊 orz。。。
用递归实现的，回头研究别人做法去。。。
代码：
/* * Author: illuz <iilluzen[at]gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: uva10020.cpp * Lauguage: C/C++ * Create Date: 2013-09-01 15:10:36 * Descripton: uva10020, minmium coverage */#include <cstdio>#include <algorithm>using namespace std;#define rep(i, n) for (int i = 0; i < (n); i++)const int MAXN = 1e5 + 1;int e, n, cnt, res[MAXN];bool flag;struct P {int l, r;} a[MAXN];bool cmp(P a, P b) {return a.l < b.l;}void solve(int i, int s) {if (s >= e) {return;}if (cnt && s < a[i].l) {flag = false;return;}if (i >= n) {flag = false;return;}int Max = a[i].r;cnt++;res[cnt - 1] = i;for (; i < n && flag; i++) {if (a[i].l <= s) {if (Max < a[i].r)Max = a[i].r, res[cnt - 1] = i;}else {if (s >= e) flag = true;else solve(i, Max);return;}}}int main() {int t;scanf("%d", &t);rep(cas, t) {scanf("%d", &e);n = 0;while(scanf("%d%d", &a[n].l, &a[n].r) && (a[n].l || a[n].r))n++;sort(a, a + n, cmp);if (cas) printf("\n");if (a[0].l > 0) {printf("0\n");continue;}flag = true;cnt = 0;solve(0, 0);if (flag) {printf("%d\n", cnt);rep(i, cnt)printf("%d %d\n", a[res[i]].l, a[res[i]].r);}else printf("0\n");}return 0;}