题解 CF865D 【Buy Low Sell High】

逃离地球

2020-11-14 22:45:11

Solution

前几天校内考试里出现了一道反悔贪心的题,我发现我还不太会这个知识点,于是来学一下。这题是反悔贪心的模板题。 ### 题意 已知 $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 数据的方式,帮助自己解决疑问,并更好的理解反悔贪心的思路。 ### 代码 ```cpp #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; } ```