【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1707
【题目大意】
每个奶牛各自能够忍受的阳光强度有一个最小值和一个最大值
防晒霜的作用是让阳光照在身上的阳光强度固定为某个值
每瓶防晒霜给出固定的阳光量和防晒霜数量,每头奶牛只能用一瓶防晒霜
问最多能晒太阳的奶牛数量
【题解】
将防晒霜的阳光固定值从小到大扫描,我们发现当这种防晒霜能满足一些牛的需求的时候,
我们应该选择优先满足最大值较低的牛的需求,这样才是更优的,
因此我们在扫描防晒霜的过程中,将所有最小值小于等于该防晒霜的牛的最大值加入优先队列,
每次出队优先队列中最小的数字去使用这个防晒霜,如果这个最小的数字比防晒霜要小,
那么这头牛在计算答案中一定是被舍弃的。
【代码】
#include <cstdio>
#include <queue>
#include <algorithm>
const int N=3000;
using namespace std;
int n,m;
typedef pair<int,int> P;
priority_queue<int,vector<int>,greater<int> > q;
P cow[N],bottle[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)scanf("%d%d",&cow[i].first,&cow[i].second);
for(int i=0;i<m;i++)scanf("%d%d",&bottle[i].first,&bottle[i].second);
sort(cow,cow+n);sort(bottle,bottle+m);
int j=0,ans=0;
for(int i=0;i<m;i++){
while(j<n&&cow[j].first<=bottle[i].first)q.push(cow[j++].second);
while(!q.empty()&&bottle[i].second){
int x=q.top(); q.pop();
if(x<bottle[i].first)continue;
ans++; bottle[i].second--;
}
}printf("%d\n",ans);
return 0;
}