量化交易题解

这是一道贪心题目，有一个神奇的贪心策略：维护一个小根堆，最小的股票价格。

若当前第 i 天的股票价格大于堆顶，那么就将差价累加到答案里，并且弹出堆顶，插入两次第 i 天的股票价格。
若小于堆顶，那么就直接插入第 i 天的股票价格。

考虑价格a<b<c，若以价格为a买入的股票在股票价格为c时卖出最优，那么能获取的利润就为c-a，如果先以股票价格为b卖出，再以股票价格为c卖出，那么利润为b-a+c-b=c-a，可以看到，这两种方法所获得的利润是一样的，b价格的股票就相当于一个中转站。但是实际上，我们并没有选择以价格b来买入股票，于是我们就需要买进两次b。

为什么最优？
　　　　　因为每次，我们相当于做了一次最优选择，将价格最低的股票以高价卖出。

附上代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll a[100005],ans;
 5 int n,cnt;
 6 
 7 int main(){
 8     while(scanf("%d",&n)!=EOF){
 9         memset(a,0,sizeof(a));
10         ans=0;
11         priority_queue<ll> q;
12         for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
13         for(int i=1;i<=n;++i){
14             if(q.empty()||a[i]<=-q.top()) q.push(-a[i]);
15             else {
16                 ans+=a[i]+q.top();
17                 q.pop();
18                 q.push(-a[i]);q.push(-a[i]);
19             }
20         }
21         printf("Case #%d: %lld
",++cnt,ans);
22     }
23     return 0;
24 }

量化交易 题解

量化交易题解