小w与炒股

发表于 |
字数统计: 347 | 阅读时长 ≈ 1
  • Code Level: ※
  • Thinking Level: ※

Description

小W卖酒小赚了一笔，决定拿着这笔钱去炒股。
他预测了某支股票后n天的价格，其中第i天股价为pi，他打算利用这个赚钱。由于他实在太懒了，每天他至多只会交易1股（也就是说，他每天可以买进一股，卖出一股，或者什么都不做）。蒟蒻最开始不拥有任何股票，他希望n天后同样不拥有任何股票，并且赚最多的钱。他希望你帮他计算最多能赚多少钱。

Solution

可以用中转站思想
对于每一站i，我们计入卖它的贡献（先计入i的值来防止负贡献，往下看），而当后面有情况j使它更优时，其优化方案也即是

(令i的票从k买来的)
可见，当i能两次被取出算贡献：在i买和在i卖得优化（前面在计算i之前先计入i得值就是这个原理）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int Nn=1e6+5;
int N;ll Ans=0;priority_queue<ll>q;
int main(){
    scanf("%d",&N); 
    for(int x,i=1;i<=N;i++){ scanf("%d",&x); q.push(-x); q.push(-x); Ans+=x+q.top(); q.pop(); }
    cout<<Ans;
    return 0;
}