POJ-3614 Sunscreen---贪心+优先队列

题目链接：

https://vjudge.net/problem/POJ-3614

题目大意：

有C个奶牛去晒太阳 (1 <=C <= 2500)，每个奶牛各自能够忍受的阳光强度有一个最小值和一个最大值，太大就晒伤了，太小奶牛没感觉。

而刚开始的阳光的强度非常大，奶牛都承受不住，然后奶牛就得涂抹防晒霜，防晒霜的作用是让阳光照在身上的阳光强度固定为某个值。

那么为了不让奶牛烫伤，又不会没有效果。

给出了L种防晒霜。每种的数量和固定的阳光强度也给出来了

每个奶牛只能抹一瓶防晒霜，最后问能够享受晒太阳的奶牛有几个。

思路：

首先能够想到的是，为了尽可能的让更多的牛能够抹上防晒油，那么我就要尽可能用高于他们忍受范围下线尽可能接近的防晒油摸他们，所以，用优先队列排牛的忍受范围下限从低到高，排列防晒油从低到高，然后从选的那些牛里面找忍受范围上限以下的防晒油给他们

 #include<iostream>

 #include<vector>

 #include<queue>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<set>

 #include<map>

 #include<cmath>

 using namespace std;

 typedef pair<int, int> Pair;

 typedef long long ll;

 const int INF = 0x3f3f3f3f;

 int T, n, m;

 const int maxn =  + ;

 Pair a[maxn], b[maxn];

 int main()

 {

     cin >> n >> m;

     for(int i = ; i < n; i++)cin >> a[i].first >> a[i].second;

     for(int i = ; i < m; i++)cin >> b[i].first >> b[i].second;

     sort(a, a + n);

     sort(b, b + m);

     int j = ;

     priority_queue<int, vector<int>, greater<int> >q;

     int ans = ;

     for(int i = ; i < m; i++)//从小到大枚举防晒霜

     {

         while(j < n && a[j].first <= b[i].first)//所有下界小于等于防晒霜的牛加入队列

         {

             q.push(a[j++].second);

         }

         while(!q.empty() && b[i].second)//当队列未空且防晒霜个数为正值时

         {

             int now = q.top();//取出当前最小的上界

             if(now >= b[i].first)//上界大于等于防暑霜，就可以直接用，小于防晒霜，那么这头牛满足不了，因为后面的防晒霜的值只会越大

             {

                 b[i].second--;

                 ans++;

             }

             q.pop();

         }

     }

     cout<<ans<<endl;

 }