AtCoder ABC250 G

贪心

线段树

记 $b[i] = -1/1/0$ 表示卖出/买入/什么都不干，再记 $s[i]$ 为 $b[i]$ 的前缀和，显然，要求 $s[i] \ge 0$ ，且答案就是 $-\sum b[i] * a[i]$

先令所有 $b[i] = 1$ ，计算出 $s[i]$ ，以 $a[i]$ 降序考虑每一个 $i$ ，把它变成 $b[i] = -1$ ，要求 $\forall j \in[i, n], s[j] \ge 2$ ；或者变成 $b[i] = 0$ ，要求 $\forall j \in[i, n], s[j] \ge 1$ ，用线段树维护，跟新即可

时间 $O(n \log n)$

贪心

然鹅不用这么麻烦，直接贪心（官方题解写的太复杂了我看了半天），用一个小根堆维护买入，对于当前天数：

若最小的买入比当前小（即可以赚），就从堆中弹出堆顶，跟新答案，然后插入两个当前天
否则，只插入一个当前天

这里插入两个当前天有点带悔贪心的味道，第一个是为了取消当前天的卖出，第二个是保证当前天可以买入

时间仍然是 $O(n \log n)$

代码

#include <bits/stdc++.h>
using LL = long long;
const int N = 2e5 + 100;
int n;
int a[N];
std::priority_queue<int> q;
LL ans = 0;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    q.push(-a[1]);
    for (int i = 2; i <= n; ++i)
    {
        if (-q.top() < a[i])
        {
            ans += a[i] + q.top();
            q.pop();
            q.push(-a[i]);
        }
        q.push(-a[i]);
    }
    printf("%lld\n", ans);
    return 0;
}