CF865D Buy Low Sell High

一种贪心策略是，对于每个数找到前面最小的没有被选择的数，如果比它小，就选择从那一天买入，这一天卖出。

hack

1
2

3
1 2 100

在 $2$ 的时候，将 $1$ 选择了。但更优的答案是在 $100$ 的时候选择 $1$ 。我们需要一个机制使得其可以反悔。设最开始在 $a$ 买入， $b$ 卖出； $a$ 买入， $c$ 卖出更优。最开始对答案的贡献为 $b - a$ ，实际最优的对答案的贡献为 $c - a$ ，两者差 $(c -a) - (b - a) = c - b$ ，相当于在 $b$ 买入，在 $c$ 卖出。所以只需要使得卖出的点又可以被买入即可反悔。

具体地，用堆维护最小值。

现在

查看代码

#include <cstdio>
#include <queue>
using namespace std;
typedef long long LL;
int n;
int main()
{
    scanf("%d", &n);
    priority_queue<int, vector<int>, greater<int>> q;
    LL res = 0;
    for (int k; n; n--)
    {
        scanf("%d", &k);
        if (!q.empty() && q.top() < k)
        {
            res += k - q.top();
            q.pop();
            q.push(k);
        }
        q.push(k);
    }
    printf("%lld", res);
    return 0;
}