首页 > 代码库 > uva10020 - Minimal coverage(区间覆盖)
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; <span style="font-family: Arial, Helvetica, sans-serif;">//更新起点</span> i--; t = -1; //更新起点后这个记录之前记录的线段就是确定需要,和更新后的没有关联了 } if (ll >= m) //能否覆盖终点 break; } if (ll < m) <span style="font-family: Arial, Helvetica, sans-serif;">//能否覆盖终点</span> 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(区间覆盖)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。