CF 865D Buy Low Sell High

题目描述

http://codeforces.com/problemset/problem/865/D

简要题意：给定接下来 $n$ 天的股票价格 $a_i$，在第 $i$ 天，你可以选择买一支彩票或者卖一支彩票或者什么都不干，求 $n$ 天后你最多赚多少

$n\le 3\times 10^5$

Solution

所以我们考虑维护一个当前可以被买入的所有东西的小根堆，每次判断卖出当前物品然后买入最便宜的东西是否赚，如果赚的话，我们就做这次生意

我们考虑如何实现反悔，我们将这次卖出的东西同样扔进小根堆里，如果之后将这个东西买入并卖出就相当于这个东西没有被买入过，即如果我们之前在 $i$ 买在 $j$ 卖，但是现在在 $i$ 买在 $k$ 卖更优，那么我们相当于获得了 $a_j-a_i+a_k-a_j=a_k-a_i$

需要注意到每次无论是否买入或卖出都需要将当前物品扔进小根堆

#include <iostream>
#include <queue>
#define maxn 300010
#define ll long long
using namespace std;

int n, a[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; priority_queue<int, vector<int>, greater<int>> Q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    ll ans = 0; 
    for (int i = 1; i <= n; ++i) {
        if (!Q.empty() && Q.top() < a[i]) {
            ans += a[i] - Q.top();
            Q.pop(); Q.push(a[i]);
        }
        Q.push(a[i]);
    } cout << ans << "\n";
    return 0;
}