首页 > 代码库 > 【单调队列】HDU 4122 Alice's mooncake shop

【单调队列】HDU 4122 Alice's mooncake shop

通道:http://acm.hdu.edu.cn/showproblem.php?pid=4122

题意:给定N和M,表示有N个订单,M个时刻可以做月饼,时刻以小时计算,任意时刻可以做若干个月饼。接着N行为N个订单的信息,包括时间和数量。再给定T和S,表示每个月饼的保质时间和每保存一小时的开销。然后M行为对应每个时刻制作月饼的代价。问说最少花费多少代价完成所有订单

思路:维护单调队列,把之前的花费大于当前的pop掉,把不满足保鲜期内的pop掉

代码:https://github.com/Mithril0rd/Rojo/blob/master/hdu4122.cpp

TAG:做懵了,感谢华哥和新哥。

【单调队列】HDU 4122 Alice's mooncake shop