Reading

CodeForces 391F3 Stock Trading

Fanyi Pu

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

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

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

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

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

用更低的买入价 x₃ 与新卖出价 x₅ 匹配横轴表示时间，纵轴表示价格。灰色点线表示原区间 x₁ 到 x₂、x₃ 到 x₄。 x₃ 的价格低于 x₁。玫瑰色虚线表示尝试将 x₁ 与 x₅ 配对， 加粗的蓝色实线表示改用 x₃ 与 x₅ 配对；后者收益更高，且能单独保留原区间 x₁ 到 x₂。价格时间x1x2x3x4x5
x3<x1，所以 x5−x3>x5−x1；[x1,x2] 可单独保留。（左右滑动查看完整图示）

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

原区间的配对关系点从左至右按时间排列，纵向位置表示价格，满足 l₁ < l₂ < r₁ < r₂。蓝色实线连接 l₁ 与 r₁，青色实线连接 l₂ 与 r₂。原区间l1r1l2r2
(r1−l1)+(r2−l2)
交换端点的配对关系所有点的位置与原图相同。蓝色实线连接 l₁ 与 r₂，可以继续合并；青色虚线连接 l₂ 与 r₁，表示单独存入 b 的收益 r₁ − l₂。交换端点l1r1l2r2
(r2−l1)+(r1−l2)
交换端点不改变总收益；虚线 [l2,r1] 表示单独计入 b 的收益 r1−l2。

根据这样两个性质，我们可以得到很多个区间。不难发现这些区间是独立的。最后我们取前 k 大的区间即可。

具体代码可以戳这里。

cpp
namespace pufanyi {
    const int maxn = 4000005;

    typedef long long LL;

    LL aa[maxn];
    LL bb[maxn];
    LL sl[maxn];
    LL sr[maxn];

    int Main() {
        int n, k;
        read(n), read(k);
        for (int i = 1; i <= n; ++i) {
            read(aa[i]);
        }
        int m = 0, tl = 0, tr = 0;
        for (int i = 1, j = 1; i <= n; i = j + 1, j = i) {
            while (j <= n && aa[j + 1] >= aa[j]) {
                ++j;
            }
            while (tl && aa[i] <= sl[tl]) {
                bb[++m] = sr[tr--] - sl[tl--];
            }
            sl[++tl] = aa[i];
            while (tr && aa[j] >= sr[tr]) {
                bb[++m] = sr[tr--] - sl[tl--];
            }
            sr[++tr] = aa[j];
        }
        while (tl) {
            bb[++m] = sr[tr--] - sl[tl--];
        }
        k = min(k, m);
        nth_element(bb + 1, bb + k, bb + m + 1, greater<LL>());
        LL ans = 0;
        for (int i = 1; i <= k; ++i) {
            if (bb[i] > 0) {
                ans += bb[i];
            }
        }
        writeln(ans);
        return 0;
    }
}

int main() {
    return pufanyi::Main();
}

Cite this post

@misc{pu2020oiicpccodeforcescf391f3,
  author = {Pu, Fanyi},
  title  = {CodeForces 391F3 Stock Trading},
  year   = {2020},
  month  = {2},
  url    = {https://pufanyi.com/blog/oi-icpc/codeforces/cf391f3}
}