Buy Low Sell High
考虑反悔贪心。
对于三个股票 \(i,j,k,p_i<p_j<p_k\),我们可以在发现有利可图时立刻卖掉 \(p_i\),然后插入 \(p_j\)(用来反悔),然后再插入一个 \(p_j\)(真正用来交易),下次遇到 \(p_k\),我们搞用来反悔的 \(p_j\),发现 \((p_k-p_j)+(p_j-p_i)=p_k-p_i\),符合要求。
注意由于只能交易一次,所以应该用 if
。(我们发现反悔实际上中途也是只能进行一次交易的)。
#include<cstdio>
#include<queue>
using namespace std;
#define Ed for(int i=h[x];~i;i=ne[i])
#define Ls(i,l,r) for(int i=l;i<r;++i)
#define Rs(i,l,r) for(int i=l;i>r;--i)
#define Le(i,l,r) for(int i=l;i<=r;++i)
#define Re(i,l,r) for(int i=l;i>=r;--i)
#define L(i,l) for(int i=0;i<l;++i)
#define E(i,l) for(int i=1;i<=l;++i)
#define W(t) while(t--)
#define Wh while
const int N=300010;
int n;
typedef long long ll;
ll ans;
priority_queue<int,vector<int>,greater<int>>q;
int main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
#endif
scanf("%d",&n);
E(i, n){
int x;
scanf("%d",&x);
if(!q.empty()&&x>q.top()){
ans+=(x-q.top());
q.pop();
q.push(x);
}
q.push(x);
}
printf("%lld",ans);
return 0;
}
标签:buy,int,top,ans,include,scanf,define
From: https://www.cnblogs.com/wscqwq/p/17724544.html