思路:
本题是一道有限队列的题目,简单的说,乳液的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; }