首页 > 代码库 > POJ 3614 Sunscreen 优先队列

POJ 3614 Sunscreen 优先队列

http://poj.org/problem?id=3614

题目大意:

给你一些母牛,母牛有能容忍日光浴的最小和最大光照强度。每只母牛可以涂一次SPF,SPF可以将母牛可以承受的光照强度固定在某个地方。现在给你母牛的最小和最大值和不同的spf的光照强度及其数量,求最多可以有多少母牛享受日光浴?

思路:

优先队列。

先按母牛最小承受的排好,然后spf的值也从小到大。

接下来用优先队列(栈顶为最小的)。对于每个spf,如果一只母牛的最小值小于等于spf则将其最大值入队。(贪心。。如两个母牛一只【1,4】一只【1,5】那么同样情况下选【1,4】不会差于【1,5】)

详见代码。



#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=2500+10;
struct cow
{
	int min,max;
	bool operator < (const cow& x)const{
		return min<x.min;
	}
}cow[MAXN];

struct spf
{
	int num,val;
		bool operator < (const spf& x)const{
			return val<x.val;
	}
}spf[MAXN];

struct data
{
	int val;
	data(int val=0) :val(val){}
	bool operator <(const data& x)const{
		return val > x.val;
	}
};
priority_queue<data> q;

int main()
{
	int c,l;
	while(~scanf("%d%d",&c,&l))
	{
		while(!q.empty())
			q.pop();

		for(int i=0;i<c;i++)
			scanf("%d%d",&cow[i].min,&cow[i].max);
		for(int i=0;i<l;i++)
			scanf("%d%d",&spf[i].val,&spf[i].num);

		sort(cow,cow+c);
		sort(spf,spf+l);

		int ans=0;
		int j=0;
		for(int i=0;i<l;i++)
		{
			while(j<c && cow[j].min <= spf[i].val)
			{
				q.push(data(cow[j].max));
				j++;
			}

			while(spf[i].num && !q.empty())
			{
				int cur=q.top().val;
				q.pop();
				if(cur < spf[i].val) continue;
				spf[i].num--;
				ans++;
			}

		}
		printf("%d\n",ans);
	}
	return 0;
}



POJ 3614 Sunscreen 优先队列