POJ 3614 Sunscreen (优先队列,贪心)
一开始用的翻译做的,可把我害惨了。然后就是读不通题意什么意思…最后无奈看了看别的大佬怎么理解的,发现翻译确实…半个小时就这样浪费了,.,…
这里是种啊,不是瓶…无语。
本来我就只是想用数组做的,然后感觉可行,也有这个想法,但是由于查题意,看见大佬的都是优先队列…优先队列是啥啊,感觉接触到了知识…于是学了学优先队列,还不错。
现在…满脑子都是优先队列解这个题了,就用优先队列做吧…
思路:
把每只cow的spfmin按升序排列(从小到大)
同理lotion也按它的spf从小到大的排列
排完后从第一种lotion开始,把spfmin小于等于lotion的牛的spfmax都放入队列里。直到没有合适的牛(例如spfmin大于第一种lotion的spf的牛)进入队列,然后进入下一步
拿出队列的第一个与第一种lotion的spf比较,小于等于答案+1,然后该种的数量减一。
直到队列为空,或者该lotion数量为0结束
这里的优先队列优先拿出队列里最小的,也就是进入队列牛的spfmax最小值
其目的是尽量把spf小的防晒霜给spfmax小的牛…
然后是下一种lotion…
//一下午就做了这一个贪心,嘛,越来越懒了
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
using namespace std;
#define maxn 2500+45
pair<int, int> cow[maxn], lotion[maxn];
priority_queue <int, vector<int>, greater<int> > q;
int c,l;
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 >> lotion[i].first >> lotion[i].second;
sort(cow, cow+c);
sort(lotion, lotion+l);
int j = 0, ans = 0;
for(int i = 0; i < l; ++i){
while(j < c&&cow[j].first <= lotion[i].first){
q.push(cow[j].second);
j++;
}
while(!q.empty()&&lotion[i].second!= 0){
int max = q.top();
q.pop();
if(max >= lotion[i].first){
lotion[i].second--;
ans++;
}
}
}
cout << ans << endl;
return 0;
}