首页 > 代码库 > UVa 10020 - Minimal coverage(区间覆盖、贪心)

UVa 10020 - Minimal coverage(区间覆盖、贪心)

算法入门经典关于区间覆盖的讲解:

8.4.6:区间覆盖问题

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

【分析】

突破口是区间的包含和排序扫描,不过要先进行一次预处理。每个区间在[s,t]外的部分应该首先被切除掉,因为他们的存在是没有意义的。在预处理后,在相互包含的情况下,小区间显然不应该考虑。

把区间按照a从小到大排序。如果区间1的七点不是s,无解,否则选择起点在s的最长区间。选择此区间[ai,bi]后,新的起点应该设置为bi,并且忽略所有区间在bi之前的部分,就像预处理一样。仍然只需要一次扫描。


题意:给予几条线段的坐标,x轴上的。求可以覆盖[0,M]线段的最少区间数和坐标。

方法和代码解释:贪心,1、先排序,左坐标小到大,右坐标从大到小。确保选到的区间是最大的。

2、注意这种情况,

        

我们选3而不选2,这就是程序中pre_l的作用。


AC代码:

#include <iostream>        
#include <iomanip>        
#include <string>        
#include <cstring>        
#include <cstdio>        
#include <queue>        
#include <stack>        
#include <algorithm>        
#include <cmath>        
#include <ctime>    

using namespace std; 

struct coo
{
	int l;
	int r;
};

const int maxn = 100000+10;

int cmp(const void *a, const void *b)
{
	coo *x = (coo *)a;
	coo *y = (coo *)b;
	if ((*x).l == (*y).l)
		return (*y).l - (*x).l;
	return (*x).l - (*y).l;
}

coo p[maxn], ans[maxn];
int main()
{
#ifdef Local
	freopen("a.txt", "r", stdin);
#endif
	int t = 0;
	cin >> t;
	while (t--)
	{
		int M = 0, num = 0, i = 0, flag = 0;//num是坐标的数量
		cin >> M;
		for (num  = 0;; num++)
		{
			cin >> p[num].l >> p[num].r;
			if (p[num].l + p[num].r == 0)
				break;
		}
		qsort(p, num, sizeof(p[0]), cmp);
		int cl = 0, cr = 0, count = 0, pre_l = 0;
		for (i = 0; i < num; i++)//遍历
		{
			if (!i && p[i].l > 0)
			{
				flag = 1;
				break;
			}
			if (p[i].r > cr)
			{
				cl = p[i].l;
				cr = p[i].r;
			}//设置为新的起点
			if (i+1 < num && p[i+1].l > pre_l)
			{
				pre_l = cr;
				ans[count].l = cl;
				ans[count].r = cr;
				count++;
				if (cr >= M)
					break;
				if (p[i+1].l > cr)
				{
					flag = 1;
					break;
				}
			}
			if (i == num - 1)
			{
				if (cr < M || p[i].l > pre_l)
					flag = 1;
				else
				{
					ans[count].l = cl;
					ans[count].r = cr;
					count++;
				}
			}
		}
		if (flag)
			cout << ‘0‘ << endl;
		else
		{
			cout << count << endl;
			for (i = 0; i < count; i++)
				cout << ans[i].l << ‘ ‘ << ans[i].r << endl;
		}
		if (t)
			cout << endl;
	}
	return 0;
}

错误:1、数组要定义在外边,因为很大,定义在里边会栈溢出。

2、p[i+1].l > cr 写错成了 > cl 。


UVa 10020 - Minimal coverage(区间覆盖、贪心)