[ABC250G] Stonks Solution

更好的阅读体验戳此进入

题面

给定序列 $P_n$$P_n$ 表示 $n$$n$ 天里的股价，每天可以买入或卖出一股，本金无限，求最多能赚多少钱。

Solution

明显反悔贪心。

不失一般性，令 $a<b<c$$a \lt b \lt c$，则若某天存在如下决策，即买 $a$$a$ 卖 $b$$b$，那么赚的钱为 $b-a$$b - a$，而显然对于 $a$$a$ 来说，若买 $a$$a$ 卖 $c$$c$，那么贡献为 $c-a>b-a$$c - a \gt b - a$，差为 $c-b$$c - b$，则不难想到当买 $a$$a$ 卖 $b$$b$ 的时候再将 $b$$b$ 插入，此时如果存在 $c$$c$ 取了插入的 $b$$b$，其实际意义即为撤销买 $a$$a$ 卖 $b$$b$ 并改为买 $a$$a$ 卖 $c$$c$，但此时 $b$$b$ 天就无操作了，所以我们此时需要再额外插入一个 $b$$b$，表示后面若需要可以执行一次买 $b$$b$ 卖 $d$$d$ 的操作。不难想到可以用小根堆维护，假设堆顶元素为 $top$$top$，当前元素为 $x$$x$，若 $x-top>0$$x - top > 0$ 那么贡献为 $x-top$$x - top$，反之将 $x$$x$ 压入小根堆即可。

双倍经验 CF865D Buy Low Sell High。

Code

xxxxxxxxxx
58
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
template < typename T = int >
23
inline T read(void);
24

25
int N;
26
int P[210000];
27
ll ans(0);
28
priority_queue < pair < int, int >, vector < pair < int, int > >, greater < pair < int, int > > > cur;
29

30
int main(){
31
    N = read();
32
    for(int i = 1; i <= N; ++i){
33
        P[i] = read();
34
        if(!cur.empty() && P[i] > cur.top().first){
35
            int val, idx; tie(val, idx) = cur.top(); cur.pop();
36
            ans += P[i] - val, cur.push({P[i], P[i]});
37
            if(idx)cur.push({idx, 0});
38
        }else cur.push({P[i], 0});
39
    }printf("%lld\n", ans);
40
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
41
    return 0;
42
}
43

44
template < typename T >
45
inline T read(void){
46
    T ret(0);
47
    int flag(1);
48
    char c = getchar();
49
    while(c != '-' && !isdigit(c))c = getchar();
50
    if(c == '-')flag = -1, c = getchar();
51
    while(isdigit(c)){
52
        ret *= 10;
53
        ret += int(c - '0');
54
        c = getchar();
55
    }
56
    ret *= flag;
57
    return ret;
58
}

UPD

update-2022_12_20 初稿