Sunscreen POJ 3614(贪心)

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <utility>
 4 #include <cstdio>
 5 #include <cmath>
 6 #include <cstring>
 7 #include <string>
 8 #include <vector>
 9 #include <stack>
10 #include <queue>
11 #include <map>
12 #include <set>
13 
14 using namespace std;
15 typedef long long LL;
16 const int INF_INT=0x3f3f3f3f;
17 const LL INF_LL=0x3f3f3f3f3f3f3f3f;
18 
19 typedef pair<int,int> P;
20 P cow[2500];
21 P lotion[2500];
22 
23 int main()
24 {
25 //    freopen("black.in","r",stdin);
26 //    freopen("black.out","w",stdout);
27     int c,l;
28     cin>>c>>l;
29     for(int i=0;i<c;i++) cin>>cow[i].first>>cow[i].second;
30     for(int i=0;i<l;i++) cin>>lotion[i].first>>lotion[i].second;
31     sort(cow,cow+c);
32     sort(lotion,lotion+l);
33     int ans=0,cnt=0;
34     priority_queue<int,vector<int>,greater<int> > que;
35     for(int i=0;i<l;i++)
36     {
37         while(cow[cnt].first<=lotion[i].first&&cnt<c) que.push(cow[cnt].second),cnt++;
38         while(que.size())
39         {
40             if(!lotion[i].second) break;
41             int p=que.top();que.pop();
42   //          printf("%d num=%d lotion %d p %d\n",i,lotion[i].second,lotion[i].first,p);
43             if(lotion[i].first<=p) lotion[i].second--,ans++;
44 
45         }
46     }
47     cout<<ans<<endl;
48     return 0;
49 }