本文共 963 字，大约阅读时间需要 3 分钟。

股票问题

题目链接：

题目大意

这道题就是一个股票，每天有价格。
可以选择买或卖或者不操作。
但一天只能买入或卖出一张。
问能获得的最大利润。

思路

我们考虑贪心。

我们可以想到，买入要低，卖出要高。
那我们可以考虑假设每一个票都买入，然后看哪些票卖出。
然后如果要卖出，就是卖出之前买入最低的那一个。
（能卖出要有股票（假设的），而且买入时价格最小的那一个要低于当前价格）
维护最低的我们可以用堆来实现。

但是有可能你枚举到后面才发现，后面有更优的，但是如果要达到最优，就要把前面已经卖出的股票选择不卖出，然后在这里卖出。
那怎么办呢？

那我们可以通过抵消的方法来搞。
我们让买入的股票价格为 $a$，第一次选择卖出是 $b$ 价格时，第二次价格是 $c$。一开始之前选的利润是 $a-b$，然后我们要让它变成 $a-c$，那就 $+b-c$。
那其实就是就算前面卖出了，也把当前价格放进去堆里面。

堆里最后会剩下一些假设买入的股票。
这些就是不买入的，就不用管。

代码

#include<queue>#include<cstdio>using namespace std;int n;long long x, ans;priority_queue <long long, vector<long long>, greater<long long> > q;int main() {   //	freopen("b.in", "r", stdin);//	freopen("b.out", "w", stdout);		scanf("%d", &n);		for (int i = 1; i <= n; i++) {   		scanf("%lld", &x);				if (!q.empty() && q.top() <= x) {   			ans += x - q.top();//在这里卖出一张股票			q.pop();			q.push(x);//假设又买进去（就是变成不买）		}				q.push(x);	}		printf("%lld", ans);		fclose(stdin);	fclose(stdout);		return 0;}