[CF865D] Buy Low Sell High - 带撤销贪心

Description

已知接下来N天的股票价格,每天你可以买进一股股票,卖出一股股票,或者什么也不做.N天之后你拥有的股票应为0,当然,希望这N天内能够赚足够多的钱

Solution

用一个堆维护当前所有买入点

扫到一个新的 \(b\)，如果堆中有比它 \(b\) 小的 \(a\)，就构成一段买卖，统计这段答案，同时将这个点 \(b\) 插入堆

如果以后我们再用这个点 \(b\) 作为买点，卖点是 \(c\)，也就意味着，我们撤掉了 \(a \to b\)，新增了 \(a \to c\)

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6 + 5;
int n;
int p[N];

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> p[i];

    priority_queue<int, vector<int>, greater<int>> que;

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (que.size() && que.top() < p[i])
        {
            ans += p[i] - que.top();
            que.pop();
            que.push(p[i]);
        }
        que.push(p[i]);
    }

    cout << ans << endl;
}