简单反悔贪心正确性证明

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$，那么得证；

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