Codeforces Round #437 E. Buy Low Sell High

题意：买卖股票，给你n个数，你可以选择买进或者卖出或者什么都不做，问你最后获得的最大收益是多少。

Examples

Input

9
10 5 4 7 9 12 6 2 10

Output

Input

20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4

Output

41
In the first example, buy a share at 5, buy another at 4, sell one at 9 and another at 12. 
Then buy at 2 and sell at 10. The total profit is  - 5 - 4 + 9 + 12 - 2 + 10 = 20.

思路：对于一个数字，如果之后的的数字如果比这个数字还大，那么我们可以当作之前买了一个，然后现在卖出去，可是这样的做
　　　 法存在问题，比如1，2，3，66，按照那样的做法，我们的收益是2-1+66-3=64，然而66-1+3-2=66，很明显是错误的。

　　　 那么，如果我们把之前的数字a放入优先队列，在遇到b的时候拿出来，把现在的数字b放入有优先队列两次，而收益暂时放
　　　 入ans中，假如说，后面有一个数字c用到了现在处于优先队列的队头b，如果我们用了这个b，实际上我们是用c买了之前的
　　　 a,原因是这样的，从收益上看，收益是c-b+(b-a)=c-a，而从优先队列上看，队列里面都是只存在b，不存在a，这样的话，
　　　 我们就是始终保持当前ans最大，并且当后面的选择与前面选择冲突的时候，让之前的选择充当一个跳板，使得我们的ans
　　　 依旧是最优的。
　　　 引用：http://blog.csdn.net/Roll_Keyboard/article/details/78145042
　　　（碰到一个大于堆顶的数，将他压入队列两次，一次是为了充当跳板，一次是本身的作用）

代码：
#include<iostream>
#include<queue>
using namespace std;

priority_queue<int,vector<int>,greater<int> >q;

int main(){
    int n,x;
    long long ans=0;
    cin>>n;
    cin>>x;
    q.push(x);
    for(int i=1;i<n;i++){
        cin>>x;
        int t=q.top();
        if(x>t){
            ans+=x-t;
            q.pop();
            q.push(x);
        }
        q.push(x);
    }
    cout<<ans<<endl;
    return 0;
}

巴特西

Codeforces Round #437 E. Buy Low Sell High

最新文章

热门文章