rt,每次默认购买这只股票,然后放到一个小根堆里,如果该元素比堆顶大就卖掉堆顶,最后弹栈退票
这样似乎每张票要么被卖掉要么被退掉,而既买又卖似乎可以合并成一个操作(这样就不用考虑多次操作的问题了),而且每次卖最小的似乎是最优的?
为啥会寄
#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#include<functional>
#define int long long
using namespace std;
int n, x, ans;
priority_queue<int, vector<int>, greater<int> >hp;
signed main()
{
scanf ("%lld", &n);
for (int i = 1; i <= n; ++ i) {
int x;
scanf ("%lld", &x);
ans -= x;
hp.push(x);
if (x > hp.top())
ans += x, hp.pop();
}
while (!hp.empty()) ans += hp.top(), hp.pop();
return printf ("%lld\n", ans), 0;
}