首页 > 代码库 > poj3614 Sunscreen 【优先队列】
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_JUDGE freopen("G:/1.txt","r",stdin); freopen("G:/2.txt","w",stdout); #endif int 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。