题目要求最大,观察数据范围,结合经验,考虑贪心。
当我们现在的烤鸡翅数量大于需求时,直接卖出。
否则,寻找前面已经卖出的最大的数量,如果该数大于当前需求,则用当前数目替代该数。
正确性不难证明:根据这个方法,我们遍历到第 $i$ 个人时,已经保证在不影响卖出人数的情况下让卖出的鸡翅数量最少。
再往后遍历时,也仍然可以保证。
这样,就实现了局部最优解向整体最优解的转变。
这个过程可以用大根堆实现。