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