《算法竞赛进阶指南》Sunscreen题解

思路：
本题是一道有限队列的题目，简单的说，乳液的spf要在奶牛的最大的spf和最小的spf之间，首先排序，将奶牛按照最小的spf从小到大排序，乳液按照spf从小到大，然后开始循环，因为之前将奶牛最小的spf从小到大排序了，那么假如奶牛的最小的spf会小于乳液的spf那么，无论后面那种乳液的spf都会符合大于最小spf这个条件，因此就可以将这只奶牛存进优先队列，然后优先队列根据奶牛的 最大的spf从小到大排序，因为小的若是符合，那么大的一定符合，但是小的不符合的情况，那么大的可能可以符合，所以为了是数量最大，那么肯定小的优先，先把难符合条件的先用了，需要注意的是乳液是有数量的，每次用完一瓶，数量要减一（代码虽然长，但是实际真正为核心的就在for循环里面的，并不难理解）。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct COW {
    int maxn;
    int minn;
};
struct Sunscreen {
    int num;
    int spf;
};
COW cow[2510];
Sunscreen sunscreen[2510];
bool cmp1(COW a, COW b) {
    return a.minn < b.minn;
}
bool cmp2(Sunscreen a, Sunscreen b) {
    return a.spf < b.spf;
}
int main() {
    int C, L;
    cin >> C >> L;
    for (int i = 0; i < C; i++) cin >> cow[i].minn >> cow[i].maxn;
    for (int i = 0; i < L; i++) cin >> sunscreen[i].spf >> sunscreen[i].num;
    sort(cow, cow + C, cmp1);
    sort(sunscreen, sunscreen + L, cmp2);
    int cnt = 0, ans = 0;
    priority_queue<int, vector<int>, greater<int> > q;
    for (int i = 0; i < L; i++) {
        while (cnt < C && cow[cnt].minn <= sunscreen[i].spf) {
            q.push(cow[cnt].maxn);
            cnt++; 
        } 
        while (!q.empty() && sunscreen[i].num) {
            int x = q.top();
            q.pop();
            if (x >= sunscreen[i].spf) {
                sunscreen[i].num--;
                ans++; 
            }
        }
    }
    cout << ans << endl;
    return 0;
}