本文主要是介绍poj3614 Sunscreen 【优先队列】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意
有C个奶牛去晒太阳 (1 <=C <= 2500)，每个奶牛各自能够忍受的阳光强度有一个最小值和一个最大值，太大就晒伤了，太小奶牛没感觉。
而刚开始的阳光的强度非常大，奶牛都承受不住，然后奶牛就得涂抹防晒霜，防晒霜的作用是让阳光照在身上的阳光强度固定为某个值。
那么为了不让奶牛烫伤，又不会没有效果。
给出了L种防晒霜。每种的数量和固定的阳光强度也给出来了
每个奶牛只能抹一瓶防晒霜，最后问能够享受晒太阳的奶牛有几个。
那么将奶牛按照阳光强度的最小值从小到大排序。
将防晒霜也按照能固定的阳光强度从小到大排序
从最小的防晒霜枚举，将所有符合 最小值小于等于该防晒霜的 奶牛的 最大值 放入优先队列之中。
然后优先队列是小值先出
所以就可以将这些最大值中的最小的取出来。更新答案。
注意priority_queue的声明priority_queue<int, vector<int>, greater<int> > que;
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
using namespace std;
const int Max = 11111;
priority_queue<int, vector<int>, greater<int> > que;
struct eg
{int x,y;
}cow[Max],bot[Max];
bool cmp(const eg& a,const eg& b)
{return a.x<b.x;
}
int main()
{#ifndef ONLINE_JUDGEfreopen("G:/1.txt","r",stdin);freopen("G:/2.txt","w",stdout);#endifint C,L;scanf("%d%d",&C,&L);for(int i=0;i<C;i++)scanf("%d%d",&cow[i].x,&cow[i].y);for(int i=0;i<L;i++)scanf("%d%d",&bot[i].x,&bot[i].y);sort(cow,cow+C,cmp);sort(bot,bot+L,cmp);int ans=0,j=0;for(int i=0;i<L;i++){while(j<C&&cow[j].x<=bot[i].x)//j牛的最小太阳量小于i防晒霜的固定量{que.push(cow[j].y);j++;}while(!que.empty()&&bot[i].y){int x=que.top();que.pop();if(x<bot[i].x)continue;ans++;bot[i].y--;}}printf("%d\n",ans);return 0;
}
这篇关于poj3614 Sunscreen 【优先队列】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
