CodeForces 391F3 Stock Trading

pufanyi

发布于：Feb 10, 2020

给出 $n\,(1\le n\le 4000000)$ 天的股票价格，每天可买进或卖出一股，可以同时买进或卖出，也可以不操作，但最终手上只能有一股。问最多 $k$ 次买进和卖出后的最大收益。

我们先来看一个 $\mathcal{O}(n\log n)$ 的做法。首先我们考虑如果是一段连续的递增股票，那我们相当于是一开始买进，最后卖出。如果这样连续的段小于等于 $k$ ，那么就直接可以返回答案了。如果比 $k$ 大，那么我们就需要做出这样两种选择：要么选择一个上升的区间放弃，要么选择一段下降的区间把两段上升的区间给连起来。这个东西我们可以用一个堆或者 set 来维护。

但是我们还有一个 $\mathcal{O}(n)$ 的做法，需要观察一些性质。我们把读入的股票看成是一个个单调不减的区间。当然有些区间可能只有一个数。

我们考虑一些区间可以合并成一个等价的区间，我们考虑将区间从左往后一个个加入。我们再开一个数组 $b$ ，记录那些不可能跟后面的区间合并的区间。

我们首先可以得到一个结论：在任一时刻对于那些可能与后面合并的区间，其买入时的价格一定是单调递增的。因为如果不是递增的，如下图情况，原来默认的匹配是 $[x_1,x_2]$ ， $[x_3,x_4]$ ，现在加入了一个右端点 $x_5$ （左端点在哪儿我们并不需要关心），如果 $x_1$ 跟 $x_5$ 配，那显然不如 $x_3$ 跟 $x_5$ 配，因为这样不仅节省了一段区间（ $[x_1,x_2]$ ），答案还更优。

我们还需要发现一个性质，那就是如果现在有两个区间 $[l_1,r_1],[l_2,r_2]$ ，如果有 $l_1<l_2$ 且 $r_1<r_2$ ，我们可以把它等价成为 $[l_1,r_2],[l_2,r_1]$ 这样两段区间。而 $[l_2,r_1]$ 是不可能再跟后面的匹配了，所以我们可以直接将其扔进 $b$ 中。