51Nod 2206 低买高卖

Problem

考虑股票市场，一共有n天。对于第i天，B君知道股票的价格是每单位a[i]元在每一天，B君可以选择买入一个单位的股票，卖出一个单位的股票，或者什么都不做。刚开始B君有无穷多的钱，但是没有任何股票。问n天之后B君最多可以赚多少钱。 (1 <= n <= 200000) (1 <= a[i] <= 10000)

Solution

一开始思路是如果四天递增，买卖买卖肯定不如买买卖卖，就从最高和最低贪心，但发现绕不过时间，就去翻题解了。

题解都是通过顺序来解决时间问题的。

变形比如只能拥有一支股票，每天可以买卖各一次，或者只能买或卖一次。做法2参考博客前面说的是哪种看不明白。

做法1：

51nod 2206 低买高卖&codeforces867E Buy Low Sell High

这个思路比较简单，如果堆空或者当前元素比堆顶元素小，就进堆，否则加入答案，弹出堆顶，进堆两次。

进堆两次是因为，如果轮到它做堆顶，再来一个最大的，可以理解为前面那次操作没有用它，正好还有一个它在堆里。如果又轮到它，就相当于又选了它。

那为什么没有第三次、第四次进堆呢？

可以看出这个数可能做一个中间量，如果第一次做完中间量以后再次成为堆中最小的，那么就必定买入，没有作为中间量的机会。

新来的更小的数或者第一个数就没有做中间量的机会。

做法2：

【51Nod 】2206 低买高卖

直接加入两次，计算答案，弹出一次。

这样一看似乎会有答案增量为负的情形，但实际不会，因为如果当前加入的是比答案小的数，它会减掉自己，增量为0，然后弹出自己，第一个数一样，其余情况转化到做法1。

第一个用iostream快，第二个改成vector快，可能是iostream对于empty有优化？

Code1

#include<iostream>
#include<stdio.h>
#include<queue>
using namespace std;
int n;
long long ans;
priority_queue<int,vector<int>,greater<int> >q;
int main(){
	scanf("%d",&n);
	int x;
	while(n--){
		scanf("%d",&x);
		if(q.empty()||x<=q.top()){
			q.push(x);
		}
		else{
			ans+=x-q.top();
			q.pop();
			q.push(x);
			q.push(x);
		}
	}
	printf("%I64d\n",ans);
	return 0;
}

Code2

#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
int n;
long long ans;
priority_queue<int,vector<int>,greater<int> >q;
int main(){
	scanf("%d",&n);
	int x;
	while(n--){
		scanf("%d",&x);
		q.push(x);
		q.push(x);
		ans+=x-q.top();
		q.pop();
	}
	printf("%I64d\n",ans);
	return 0;
}