量化交易

量化交易

（Lg题目有问题，会TLE）

https://codeforces.com/problemset/problem/865/D CF上AC

https://www.cnblogs.com/Yuzao/p/6886194.html

两个操作：

1、第j天买入

2、第i天卖出(j<i)

用一个小根堆维护，j 就取堆顶，每次对ans贡献为 a[i]-a[j]

第i天卖出可能不够优，可能之后又涨价了，那么执行贪心的反悔操作，把a[i] push两遍，意思是比如你第i天卖出，而后边的第k天(i<k) 又涨价，那你push两遍后对ans 的贡献为 a[i]-a[j]+a[k]-a[i]=a[k]-a[j]还是相当于第k天卖出

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
priority_queue< ll,vector<ll>,greater<ll> > h;
ll n,m,ans,x,t;
int main() {
	int cnt=1;
	while(scanf("%d",&n)!=EOF) {
		ans=0;
		while(!h.empty()) h.pop();
		for(int i=1;i<=n;i++) {
			scanf("%d",&x);
			if(h.empty()||h.top()>=x)
				h.push(x);
			else {
				t=h.top();
				h.pop();
				ans+=x-t;
				h.push(x);//买入
				h.push(x);//反悔
			}
		}
		printf("Case #%d: %lld
",cnt++,ans);
	}
	return 0;
}