BISHI51　低买高卖¶

中等通过率 47.36%python3样例通过牛客 AC

牛客原题　源码

讲解章节：优先队列与堆、贪心

一句话

每天至多买/卖 1 股，最后必须清仓，求最大收益。

解题思路¶

这题考什么¶

经典「反悔贪心」（CF865D Buy Low Sell High）。因为每天只能动 1 股、最后必须清空，所以答案等价于：把 n 天拆成若干组 (买日, 卖日) 的匹配，每组贡献 p_卖 - p_买，且同一天最多出现在一组里。

贪心做法：维护一个小根堆，堆里存「当前可以被卖掉的买入价」。第 i 天价格 p：

若堆顶 t < p，说明「以 t 买、今天 p 卖」立刻赚 p - t，先吃下这笔；
吃完后再把 p 额外压一次堆。这第二个 p 就是「反悔票」：若以后出现更高价 q，用它成交时 ans 会再加 q - p，两笔合起来是 (p - t) + (q - p) = q - t，等价于「其实当初那股应该留到 q 天再卖」。也就是说压两次 p 让贪心具备了撤销能力，所以局部最优即全局最优。
无论是否成交，都把 p 压一次堆（它自身也可以作为未来的买入价）。

数据规模与复杂度¶

n <= 3e5。O(n^2) 的区间 DP / 二分图匹配都不可能；本做法 O(n log n) ≈ 3e5 * 19，heapq 底层是 C 实现，毫秒级。

坑在哪¶

必须压两次（一次「反悔票」+ 一次「自身作为买点」），只压一次就退化成「只能做一笔」的错解；
「第 n 天必须清仓」这个约束不需要额外处理：贪心里每一次收益都是由一买一卖配对产生的，堆里剩下的都是从没买过的价格，天然平仓；
收益最大可达 3e5/2 * 1e6 ≈ 1.5e11，C++ 要 long long，Python 无所谓；
判定写 h[0] < p 而不是 h[0] <= p：等价时收益为 0，成交与否结果一样，但成交会白白多做一次堆操作。

样例复核¶

p = [10,5,4,7,9,12,6,2,10]，逐日跟踪堆顶与累计收益： 10、5、4：堆顶都不小于当日价，只压入，堆 = {4,5,10}； 7：堆顶 4 < 7，吃掉 7-4 = 3（累计 3），压入两个 7； 9：堆顶 5 < 9，吃掉 9-5 = 4（累计 7）； 12：堆顶是上一步留下的反悔票 7，吃掉 12-7 = 5（累计 12）——

这一笔与前面的 3 合起来正是「4 买、12 卖」的 8；

6、2：堆顶不小于当日价，只压入； 10：堆顶 2 < 10，吃掉 10-2 = 8（累计 20）。答案 20，与题面给出的 (9-5)+(12-4)+(10-2) = 20 一致 —— 中间过程的配对与题面方案并不相同，反悔票让两者总额殊途同归。

堆的用法见 35-优先队列与堆，反悔贪心的一般套路见 47-贪心。

参考实现¶

solutions/BISHI51.py
import heapq
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    ans = 0
    h = []                      # 小根堆：所有「可以被今天卖掉」的候选买入价
    # 绑成局部名字，省掉循环里每次的属性查找
    push, pop = heapq.heappush, heapq.heappop
    for tok in data[1:n + 1]:
        p = int(tok)
        if h and h[0] < p:      # 堆顶是最便宜的买点，能赚才成交
            ans += p - pop(h)
            push(h, p)          # 反悔票：允许把这笔交易的卖出价往后挪
        push(h, p)              # p 自身也可以充当未来的买入价
    sys.stdout.write(str(ans) + "\n")


main()

BISHI51 低买高卖¶