求助这个思路为什么是错的
查看原帖
求助这个思路为什么是错的
563650
haochengw920楼主2024/5/31 09:40

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;
}
2024/5/31 09:40
加载中...