CodeForces - 867E （贪心+优先队列）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了CodeForces - 867E （贪心+优先队列），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1123字，纯文字阅读大概需要2分钟。

内容图文

时隔多日，再来补题。
我们都知道股票的价格时涨时跌，想要赚钱的话，就要在他跌了的时候买入，在他涨了的时候卖掉，
现在就是，我们知道每天的股票的价格，问能获得的最大利润是多少？

解题思路

我想的解题思路就是，贪心再加上优先队列
就是假设每天都买入，然后放在优先队列里排好序，如果对头的元素（也就是股票最便宜的价格）小于今天的价格，那就卖出，然后把今天卖掉的价格再加到队列中去，
很简单的理解就是如果a<b<c;我们第一天买入的时候是a，然后第二天变成b了，那我们就卖出，那么得到的利润就是b-a，记录下来再把b加入队列，表示今天买的，然后第三天价格是c，更高了，那么我们再卖出得到的利润就是c-b；那么其实得到的总的利润就是（c-b）+（b-a）=c-a；中间相当于做了一次无用的买卖（以b的价格买入）。

输入样例

样例1：
9
10 5 4 7 9 12 6 2 10
样例2：
20
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4

输出样例

样例1：20
样例2：41

AC代码

#include<bits/stdc++.h>

using namespace std;
#define  int long long
const int maxn=3e5+10;

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

signed main()
{
    int n;
    cin>>n;
    int m;
    int ans=0;
    for(int i=0; i<n; i++)
    {
        cin>>m;
        if(qu.size()&&m>qu.top())//表示卖出
        {
            ans+=(m-qu.top());
            qu.pop();
            qu.push(m);
        }
        qu.push(m);//每天都买入
    }
    cout<<ans<<endl;
}

内容总结

以上是互联网集市为您收集整理的CodeForces - 867E （贪心+优先队列）全部内容，希望文章能够帮你解决CodeForces - 867E （贪心+优先队列）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---