题目大意

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

题解

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

　　

转载于:https://www.cnblogs.com/headboy2002/p/9184696.html

总结

以上是生活随笔为你收集整理的luogu3093 牛奶调度的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。