luogu3093 牛奶调度

题目大意

　　有一些奶牛，它们能挤出不同数量的奶，要想挤它要在其所对应的最后期限前完成。一个时间点只能挤完一个奶牛。问最多能挤出多少奶？

题解

　　如果我们要挤一个奶牛，我们要让他越晚被挤越好，这样构成最优解的奶牛被选中的可能性最大。因此我们把所有奶牛按照最后期限从高到低一个个遍历（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
", ans);
	return 0;
}