题解 CF865D 【Buy Low Sell High】

· · 题解

前几天校内考试里出现了一道反悔贪心的题，我发现我还不太会这个知识点，于是来学一下。这题是反悔贪心的模板题。

题意

已知 n 天内的股票价格，每一天可以选择买进、卖出或不做，最初有无限的钱，最大化收益。n\le 3\times 10^5。

题解

一个简单的贪心想法就是把每一天都看作一个物品，从前向后遍历每一天并在所有可选的物品中选择价格最小的，并获得两个股票价格之差的收益。

但是这个贪心并没有考虑这样的选择对后面的影响，比如，这样一组数据就可以卡掉这个贪心：

3
1 2 100

我们选择让 2 与 1 获得 1 的收益，而使 100 无法获得收益。但事实上 100 与 1 可以获得 99 的收益，显然更优。

于是我们考虑修正这个做法，加上一个「反悔」的操作。具体来说，我们对于每一个形如「在第 i 天买入，在第 j 天卖出」的决策，假想出一个价格为 val 的物品，使得「在第 i 天买入，在第 j 天卖出，同时买入这个价格为 val 的物品，并在第 k 天卖出」，等价于「在第 i 天买入，在第 k 天卖出」。这样，我们选择买入这样一个物品，也就相当于撤销了「在第 i 天买入，在第 j 天卖出」这个决策，而改为「在第 i 天买入，在第 k 天卖出」，反悔操作得以实现。

那么这个物品的价值 val 究竟应该是多少呢？设第 i 天的价格为 a_i，则有 a_j-a_i+a_k-val=a_k-a_i，化简得 val=a_j。于是，我们便设计出了一个新的算法：维护一个可重集合，代表「可选的物品的价格」。从前向后遍历每一天，对于第 i 天，找到集合中最小的价格 a_j，并向集合中插入 a_i，代表 a_i 这一天可选。若 a_i>a_j，则把答案加上 a_i-a_j，并向集合中再次加入 a_i，代表假想的反悔物品，并将 a_j 从集合中删除。我们可以使用堆维护这个集合，时间复杂度 \mathcal{O}(n\log n)。

为了保证这个算法的正确性，我们还要解决如下几个问题：

Q1：如果我只选了那个可选物，而不选反悔物，那么这一天岂不是又买入又卖出？与题意不符。

A1：事实上，由于可选物与反悔物的价格相同，我们可以认为优先选择反悔物，而不会出现冲突。

Q2：为何被反悔的物品不能选择一个次优的物品买入？在此算法中一个物品被反悔后只能作为价格低的物品被买入。

A2：我们可以注意到，一个物品的决策被反悔当且仅当它是这个集合中最小的数，即没有比它更小的数供它选择买入、同时也没有比它更小的，在它后面的数抢它的东西。

Q3：为何一个物品不被反悔就只能作为较大数卖出？这个物品作为较小数买入为何不可能更优？

A3：因为一个物品被反悔与一个物品作为较小数买入更优的条件一样。

事实上，本题的反悔贪心做法正确性不是非常显然，大家应该仔细思考，对于自己的疑点，通过尝试制造 Hack 数据的方式，帮助自己解决疑问，并更好的理解反悔贪心的思路。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int read() {
    int ret = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') f = (ch == '-') ? -f : f, ch = getchar();
    while (ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = getchar();
    return ret * f;
}

int n, ans;
priority_queue<int, vector<int>, greater<int> > q;
signed main() {
    n = read();
    for (int i = 1; i <= n; ++i) {
        int k = read();
        if (!q.empty() && q.top() < k) ans += k - q.top(), q.pop(), q.push(k);
        q.push(k);
    }
    printf("%lld\n", ans);
    return 0;
}