UVa 10020 (最小区间覆盖) Minimal coverage

时间:2022-01-05 18:08:44

题意:

数轴上有n个闭区间[ai, bi],选择尽量少的区间覆盖一条指定线段[0, m]

算法:

[start, end]为已经覆盖到的区间

这是一道贪心

把各个区间先按照左端点从小到大排序,更新start为end,如果区间1在start的右端,则无解,因为其他区间更不可能覆盖到

然后在剩下的能覆盖到start的区间里面选择能覆盖到最右端的区间并更新end,然后记录在path里面。如果end的已经将m覆盖则退出循环

如果遍历完所有的区间后end依然没能覆盖到start,则无解

最后按照parh里面记录的路径输出区间即可

 //#define LOCAL
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = + ; struct Range
{
int a, b;
inline bool operator< (const Range& rhs) const
{
return a < rhs.a || (a == rhs.a && b < rhs.b);
}
}ranges[maxn];
int path[maxn]; int main(void)
{
#ifdef LOCAL
freopen("10020in.txt", "r", stdin);
#endif int T;
scanf("%d", &T);
while(T--)
{
int a, b, m, n = ;
scanf("%d", &m);
while(scanf("%d%d", &a, &b) == )
{
if(a == && b == ) break;
if(a > m) continue;
if(a < ) a = ;
ranges[n].a = a;
ranges[n++].b = b;
}
sort(ranges, ranges + n);
int minCover = ;
int start = , end = ;
for(int i = ; i < n; )
{
start = end;
if(ranges[i].a > start)
break;
while(i < n && ranges[i].a <= start)
{
if(ranges[i].b > end)
{
end = ranges[i].b;
path[minCover] = i;
}
++i;
}
++minCover;
if(end >= m) break;
}
if(end < m) minCover = ;
printf("%d\n", minCover);
for(int i = ; i < minCover; ++i)
printf("%d %d\n", ranges[path[i]].a, ranges[path[i]].b);
if(T)
printf("\n");
}
return ;
}

代码君