Gravatar
yrtiop
积分:2101
提交:309 / 808

题目要求最大,观察数据范围,结合经验,考虑贪心。

当我们现在的烤鸡翅数量大于需求时,直接卖出。

否则,寻找前面已经卖出的最大的数量,如果该数大于当前需求,则用当前数目替代该数。

正确性不难证明:根据这个方法,我们遍历到第 $i$ 个人时,已经保证在不影响卖出人数的情况下让卖出的鸡翅数量最少。

再往后遍历时,也仍然可以保证。

这样,就实现了局部最优解向整体最优解的转变。

这个过程可以用大根堆实现。


题目2235  烤鸡翅 AAAAAAAAAA      15      评论
2021-12-22 13:22:58