当前位置: 代码迷 >> 综合 >> Codeforces Round #437 (Div. 2)E. Buy Low Sell High(优先队列)
  详细解决方案

Codeforces Round #437 (Div. 2)E. Buy Low Sell High(优先队列)

热度:23   发布时间:2023-12-17 03:42:42.0

题意:

给你n个数字,现在你可以有以下的操作,买一个数字,再在之后卖出去,问最多能赚多少钱

思路:

对于一个数字,如果之后的的数字如果比这个数字还大,那么我们可以当作之前买了一个,然后现在卖出去,可是这样的做法存在问题,比如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依旧是最优的

错误及反思:

0(看了看榜,感觉要是打了这场CF就能疯狂上分,只能叹息午夜场肝不动啊)

代码:

#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
int main()
{int n;scanf("%d",&n);long long ans=0;int x;for (int i=0;i<n;i++){scanf("%d",&x);if(q.empty()){q.push(x);continue;}if(x<=q.top())q.push(x);else{ans+=(x-q.top());q.pop();q.push(x);q.push(x);}}printf("%I64d\n",ans);return 0;
}
  相关解决方案