POJ 3614 优先队列

题目链接:http://poj.org/problem?id=3614

有 $C$ 头牛去晒太阳,可牛承受不住如此的阳光强度,于是他们都需要防晒霜。

每种防晒霜有两个属性:数量和 $SPF$(可以理解为防晒强度,太小没效果,太大就等于没晒太阳)

每头牛各自都有对 SPF 的一个期望范围:$1 \leq minSPF_i \leq maxSPF_i \leq 1,000$。

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

思路

假设我们把所有防晒霜的 $SPF$ 从小到大排序后依次考虑。

倘若我们目前正在考虑的防晒霜为第 $i$ 个,所有愿意使用这款防晒霜的牛(即 $minSPF_j \leq SPF_i \leq maxSPF_j$)组成的集合为 $Set$,那我们一定优先从这个集合中选取 $maxSPF$ 小的奶牛。(因为防晒霜的 $SPF$ 是递增的,必须先满足 $maxSPF$ 小的奶牛)

因此将所有奶牛按 $minSPF$ 为第一关键字,$maxSPF$ 为第二关键字,对于某种防晒霜,将所有满足 $minSPF < SPF$ 的奶牛放入优先队列(小顶堆)中,再从优先队列中依次取出 $maxSPF$ 最小的奶牛给与防晒霜。

3614.cppview raw
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <queue>
#define maxn 3000
#define maxm 3000
using namespace std;

priority_queue<int, vector<int>, greater<int> > q;
pair<int, int> cow[maxn], lotion[maxm];
int n, m;

int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++)
scanf("%d %d", &cow[i].first, &cow[i].second);
for (int i = 0; i < m; i++)
scanf("%d %d", &lotion[i].first, &lotion[i].second);
sort(cow, cow + n);
sort(lotion, lotion + m);
int ans = 0;
for (int i = 0, j = 0; j < m; j++) {
while (i < n && cow[i].first <= lotion[j].first)
q.push(cow[i++].second);
while (!q.empty() && lotion[j].second) {
if (q.top() >= lotion[j].first) {
lotion[j].second--;
ans++;
}
q.pop();
}
}
printf("%d\n", ans);
return 0;
}