本文主要是介绍uva10020 - Minimal coverage（区间覆盖），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：uva10020 - Minimal coverage（区间覆盖）
题目大意：给出一些线段，然后问怎样取能使得最少的线段覆盖区间[0, M].
解题思路：先预处理掉那些和区间【0，M】不沾边的线段。
将线段按照起点小的排序。
接着遍历这些线段。首先先判断起点最小的点是否<=0,如果不满足这个说明它不能覆盖区间。
然后每次都小于等于当前覆盖的起点的最长线段，之后要将起点更新成这个最长线段的终点。然后接着判断下一条线段。如果更新了起点发现依然找不到满足条件的线段，说明不能覆盖。
最后还要看一下是否能够覆盖到M。
代码：
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;const int N = 100005;
int m, n;
int visit[N];struct segments {int l, r;
}s[N];int cmp (const segments& a, const segments &b) { return a.l < b.l; }int Max (const int a, const int b) {return a > b ? a: b;}int solve () {memset (visit, 0, sizeof (visit));if (s[0].l > 0) //判断能否覆盖区间起点return 0;int st = 0;int ll = -1;int t = -1;for (int i = 0; i < n; i++) {if (s[i].l <= st) { //找符合条件的最长的线段if (ll < s[i].r) {visit[i] = 1;if (t >= 0)visit[t] = 0;t = i;ll = Max (ll, s[i].r);}} else { if (st == ll) //更新后发现依然没有return 0;st = ll; //更新起点i--;t = -1; //更新起点后这个记录之前记录的线段就是确定需要，和更新后的没有关联了 }if (ll >= m) //能否覆盖终点break;}if (ll < m) //能否覆盖终点return 0;int count = 0;for (int i = 0; i < n; i++)if (visit[i])count++;return count;
}int main () {int t;int l, r;scanf ("%d", &t);while (t--) {scanf ("%d", &m);n = 0;while (scanf ("%d%d", &l, &r), l || r) {if (r <= 0 || l >= m)continue;s[n].l = l;s[n].r = r;n++;}sort (s, s + n, cmp);int count = solve();printf ("%d\n", count);if (count) {for (int i = 0; i < n; i++)if (visit[i])printf ("%d %d\n", s[i].l, s[i].r);}if (t)printf ("\n");}return 0;
}这篇关于uva10020 - Minimal coverage（区间覆盖）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
