POJ 3614
题意：有C头牛 L 种 防晒霜，C头牛有最大和最小的承受防晒范围，L种防晒是有自己的固定值和n瓶，求多少牛可以晒太阳。
说实话：此题优先队列是为贪心而准备的。
贪心？就是从最小的防晒霜开始找，找C头牛范围小的。
想要求出最多的牛晒太阳，当然是从最小的开始遍历。
#include<iostream> #include<queue> #include<vector> #include<algorithm> using namespace std; typedef pair<int ,int > p; <span style="font-family:Courier New;">//可以看成结构体</span> p cow[2500],bot[2500]; priority_queue <int ,vector<int>,greater<int> >q; int main() { int c,l; 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>>bot[i].first>>bot[i].second; sort(cow,cow+c); sort(bot,bot+l); int j = 0,ans = 0; for(int i = 0;i < l; i++){ while(j < c && cow[j].first <= bot[i].first){ q.push(cow[j].second); j++; } while(!q.empty() && bot[i].second){ int x = q.top(); q.pop(); if(x < bot[i].first) continue; ans++; bot[i].second--; } } cout<<ans<<endl; return 0; }
用结构体写：
#include<iostream> #include<queue> #include<vector> #include<algorithm> using namespace std; class p { public: int first; int second; }; bool cmp(p a,p b) { return a.first<b.first; } p cow[2500],bot[2500]; priority_queue <int ,vector<int>,greater<int> >q; int main() { int c,l; 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>>bot[i].first>>bot[i].second; sort(cow,cow+c,cmp); sort(bot,bot+l,cmp); int j = 0,ans = 0; for(int i = 0;i < l; i++){ while(j < c && cow[j].first <= bot[i].first){ q.push(cow[j].second); j++; } while(!q.empty() && bot[i].second){ int x = q.top(); q.pop(); if(x < bot[i].first) continue; ans++; bot[i].second--; } } cout<<ans<<endl; return 0; }
