简单反悔贪心正确性证明

· · 个人记录

CF865D Buy low sell high

首先有贪心：将每个价值压入堆，如果当前价值大于根，那么就弹根并贡献。

但是这样是错误的：1 2 100，正确答案应当是 99。

我们需要一个反悔的操作：注意到 p_i - p_o + p_j - p_i = p_j - p_o，即以 i 做一个中转点。

形式化些，每次购买，弹根的同时，要将自己的价值也压入其中，提供反悔的机会。

考虑正确性。我们要证：不存在任意时刻 (x, y)（ 表示 x, y 之间的差价）在最优方案中，而不在上文所述的反悔谈心方案中。

我们有：对于所有不是买进点的 i \lt x, p_i \gt p_x。如果 i 是卖出点，我们将其与 y 连接得到不劣的方案；如果 i 时刻什么都不做，那么我们与 y 连起来显然更优。

那么，x 一定是当前堆的堆顶，因此我们一定有一个 x \lt f \le y, p_f \gt p_x，那么 f 将 x 弹出，同时 f 被压入。如果 f 是 y，那么得证；

麻了，发现太显然了，不想证了。读者自证。