可反悔贪心-codeforce 867E - Buy Low Sell High题意思路代码

81 阅读 0 评论 54 点赞

我是靠谱客的博主无心画板，最近开发中收集的这篇文章主要介绍可反悔贪心-codeforce 867E - Buy Low Sell High题意思路代码，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意

已知接下来N天的股票价格,每天你可以买进一股股票,卖出一股股票,或者什么也不做.N天之后你拥有的股票应为0,当然,希望这N天内能够赚足够多的钱.
输入:
第一行一个整数天数N(2<=N<=300000).
第二行N个数字 $p_1,p_2...p_N(1<=pi<=10^6)$ ,表示每天的价格.
输出: N天结束后能获得的最大利润.

思路

这种可反悔式的贪心算法，就是使用一个堆结构记录之前的贪心后的状态，这个状态需要有一种可逆的操作，也就是一种修正的性质，使得之后如果遇到更优的解的时候，能够把之前的贪心地局部最优解替换成的当前最优解。
回到这道题上，我们可以使用优先级队列来记录之前 $i$ 天的价格，我们一个很直接的思路是，如果当前的 $p r i c e s [i]$ 大于之前优先级队列中的最小值，那么我们可以直接取他们之间的差值作为一种决策（在最小值那天买入，在当前天进行卖出），那么能够获得当天的利润最大值。但是之后可能会有更优的解，我们需要在队列中记录当前贪心的中间结果，如何记录呢？那就是如果当前天能够进行一次贪心操作，那么将这天的prices[i]再次放入队列中，以便之后的反悔更新操作。下面举一个例子：
对于[3,7,10,20]这个股票价格：

对于3来说，直接入队[3]
对于当前的7，首先入队[3,7],然后队首的3比7小，进行一次贪心操作ans+=7-3，把当前的7再次入队，得到最终的[7,7]
对于10，首先入队[7,7,10],然后队首的7比10小，进行一次贪心操作ans+=10-7，把当前10再次入队，得到[7,10,10] 这里很明显地看出贪心反悔的操作了，之前答案ans进行贪心添加了一次7-3,同时将7再次假如到队列，使得这次10找到7进行贪心操作添加了10-7，即ans+=7-3+10-7=10-3,这样成功进行了一次反悔操作。
最后对于20,贪心ans+=20-7 入队[10,10,20]，之所以对于每个元素最多放入队列两次，一次是为了贪心地反悔，另一次是真正的卖出。

代码

void B(){
    //B - Buy Low Sell High CodeForces - 867E
    int n;
    cin>>n;
    ll res=0;
    vector<ll> a(n,0);
    for(int i=0;i<n;i++) cin>>a[i];
    priority_queue<ll,vector<ll>,greater<ll>> que;
    for(int i=0;i<n;i++){
        que.push(a[i]);
        if(!que.empty()&&que.top()<a[i]){
            res+=a[i]-que.top();
            que.pop();
            que.push(a[i]);
        }
    }
    cout<<res<<endl;
}