题目大意
有一些奶牛，它们能挤出不同数量的奶，要想挤它要在其所对应的最后期限前完成。一个时间点只能挤完一个奶牛。问最多能挤出多少奶？
题解
如果我们要挤一个奶牛，我们要让他越晚被挤越好，这样构成最优解的奶牛被选中的可能性最大。因此我们把所有奶牛按照最后期限从高到低一个个遍历（1）。当同一个时间点有多个奶牛时，我们挤那个奶数最多的牛（2）。注意：同一时间点其它的奶牛怎么办？我们不能把这些奶牛放弃不管了。我们应当把它的最后期限-1继续操作（操作*）。
奶数最多的牛需要用优先队列来维护。注意：不用一下子就把所有牛都推进去同时实现（1）（2），这样我们实现操作*的方法就是把牛的最后期限-1再推入队列。此方法不开O2过不了，因为队列内数据量太大，push,pop操作又太多。因此我们只需要让当最后期限相等的情况下，只让队列实现（2）即可。也就是说对于一个最后期限，我们只取堆顶的奶牛，剩余的奶牛仍然保留在堆中，直接进行最后期限小1的操作，相当于没被挤到的奶牛的最后期限。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cassert>
using namespace std; const int MAX_COW = 100010, INF = 0x3f3f3f3f; struct Cow
{
int Deadline, W; bool operator < (const Cow& b) const
{
return W < b.W;
}
}_cows[MAX_COW]; bool cmp(Cow a, Cow b)
{
return a.Deadline < b.Deadline;
} int main()
{
int totCow, maxt = 0;
scanf("%d", &totCow);
for (int i = 1; i <= totCow; i++)
{
scanf("%d%d", &_cows[i].W, &_cows[i].Deadline);
maxt = max(maxt, _cows[i].Deadline);
}
sort(_cows + 1, _cows + totCow + 1, cmp);
static priority_queue<Cow> q;
int curCow = totCow;
int prevDeadline = INF, ans = 0;
for (int i = maxt; i >= 1; i--)
{
while (_cows[curCow].Deadline == i)
q.push(_cows[curCow--]);
if (!q.empty())
{
ans += q.top().W;
q.pop();
}
}
printf("%d\n", ans);
return 0;
}