POJ2376Cleaning Shifts(区间覆盖贪心)

应该还是蛮简单的一题，但是因为模拟太差，一直没调出来.......

\(显而易见的应该按照左区间从小到大排序，相等按照右区间大到小排序\)。

\(那么第一个区间的l一定要是1，而且必拿(否则没有区间能包括1)\)

\(往后找一个R尽可能大的区间，前提是L被我们上一个选的区间的R+1包括\)

\(重复\)

细节还比较多，我还是太菜了啊

#include <bits/stdc++.h>

using namespace std;

struct p{

	int l,r;

}b[25009],a[25009];int n,t,cnt;

bool com(p a,p b){

	if(a.l==b.l)	return a.r>b.r;

	else	return a.l<b.l;

}

void last(){

	cout<<-1;

	exit(0);

}

int main()

{

	cin>>n>>t;

	for(int i=1;i<=n;i++)

	{

		cin>>b[i].l>>b[i].r;

		if(b[i].l<1)	b[i].l=1;

	}

	sort(b+1,b+1+n,com);b[0].l=-1;

	for(int i=1;i<=n;i++)

		if(b[i].l!=b[i-1].l)	a[++cnt]=b[i];//选取L相同时区间中的最优区间。不放到a数组里面也没事

	if(a[1].l!=1)	last();

	int ans=1,tim,zan,i=1,num,flag;

	while(1)

	{

		zan=a[i].r,tim=a[i].r,i++,flag=0;

		if(tim>=t)	break;

		if(i>=cnt+1)	last();

		while(i<=cnt&&a[i].l<=tim+1)

		{

			if(zan<a[i].r)

				flag=1,zan=a[i].r,num=i;

			i++;

		}

		if(flag==0)	last();

		i=num,ans++;

	}

	cout<<ans;

}

然后下面是借鉴别人改进过的写法

#include <iostream>

#include <algorithm>

#include <string>

#include <cstdio>

using namespace std;

struct p{

	int l,r;

}b[25009],a[25009];int n,t,cnt;

bool com(p a,p b){

	if(a.l==b.l)	return a.r>b.r;

	else	return a.l<b.l;

}

int main()

{

	cin>>n>>t;

	for(int i=1;i<=n;i++)

	{

		cin>>b[i].l>>b[i].r;

		if(b[i].l<1)	b[i].l=1;

	}

	sort(b+1,b+1+n,com);b[0].l=-1;

	for(int i=1;i<=n;i++)

		if(b[i].l!=b[i-1].l)	a[++cnt]=b[i];

	int maxn=0,minn=0,top=1,ans=0;

	while(maxn<t)

	{

		minn=maxn+1;//上一次覆盖的区间+1

		for(int i=top;i<=cnt;i++)

		{

			if(a[i].l>minn)

			{

				top=i;

				break;

			}

			else

				maxn=max(maxn,a[i].r);

		}

		if(maxn==minn-1)	break;//匹配失败

		ans++;

	}

	if(maxn>=t)	cout<<ans;

	else	cout<<-1;

}

巴特西

POJ2376Cleaning Shifts(区间覆盖贪心)

最新文章

热门文章