【POJ - 3614】Sunscreen (优先队列)
Sunscreen
Descriptions
C (1 ≤ C ≤ 2500) 头奶牛在海滩边晒太阳,要避免在日光浴时产生难看的灼伤,每头奶牛必须用防晒霜覆盖它的皮肤。第 i 头奶牛有一个最小和最大 SPF 值 (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) 将会起作用。如果 SPF 值太低,则奶牛会受到日光灼伤;如果 SPF 值太高,则牛奶无法进行日光浴。
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。奶牛们有一个野餐篮子,带了 L (1 ≤ L ≤ 2500) 瓶防晒霜乳液,第 i 瓶的 SPF 值是 SPFi(1 ≤ SPFi ≤ 1,000) 。第 i 瓶防晒霜可以涂抹覆盖 coveri 头奶牛。一头牛奶只能用一瓶防晒霜涂抹。
对于给定的防晒霜乳液,最多可以有多少头奶牛能够在日光浴时避免被灼伤?
输入
* 第 1 行: 两个以空格分隔的整数: C 和 L
* 第 2 到 C+1 行: 第 i 行描述了第 i 头奶牛的防晒霜约束条件,包括两个整数: minSPFi 和 maxSPFi
* 第 C+2 到 C+L+1 行: 第 i+C+1 行描述了第 i 个防晒霜瓶,包括以空格分隔的整数: SPFi和 coveri
输出
只包含一个整数的单行,表示日光浴时受到防晒保护的奶牛的最大数量。
示例输入
3 2 3 10 2 5 1 5 6 2 4 1
示例输出
2
题目链接
https://vjudge.net/problem/POJ-3614
将奶牛按照SPF值的最小值从小到大排序。
将防晒霜也按照SPF的值从小到大排序
从最小的防晒霜枚举,将所有符合 最小值小于等于该防晒霜的奶牛的最大值 放入优先队列之中。
然后优先队列是小值先出
priority_queue<int, vector<int>, greater<int> > qi2;//从小到大的优先级队列,可将greater改为less,即为从大到小
AC代码
#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <sstream> #define IOS ios_base::sync_with_stdio(0); cin.tie(0); #define Mod 1000000007 #define eps 1e-6 #define ll long long #define INF 0x3f3f3f3f #define MEM(x,y) memset(x,y,sizeof(x)) #define Maxn 100000+5 using namespace std; int C,L; typedef pair<int,int> P; priority_queue<int,vector<int>,greater<int> >q;//优先队列 P cow[Maxn],sun[Maxn];//奶牛 防晒霜 int main() { cin>>C>>L; for(int i=0;i<C;i++)//存数据 cin>>cow[i].first>>cow[i].second; for(int i=0;i<L;i++) cin>>sun[i].first>>sun[i].second; sort(cow,cow+C);//排序 sort(sun,sun+L); int j=0,ans=0; for(int i=0;i<L;i++) { while(j<C&&cow[j].first<=sun[i].first)//奶牛FPS最小值小于防晒霜的FPS { q.push(cow[j].second);//奶牛入队 j++; } while(!q.empty()&&sun[i].second) { int now=q.top(); q.pop(); if(now<sun[i].first)//奶牛FPS最大值小于防晒霜的FPS,不符合 continue; ans++;//若符合,则奶牛数+1 sun[i].second--;//防晒霜数量-1 } } cout<<ans<<endl; return 0; }