模拟赛题讲解[18]

来自 yukuai26 2022-08-08 noi.ac #2773

题目背景：

搞个大新闻. jpg

题目描述：

你来到了幻想乡。首先你准备搞一个大新闻，获得文文的报道并变得出名，你决定对幻想乡的股票系统下手。

你通过猪脚光环了解到了接下来 $n$ 天的股票价格 $a_i$，你每天可以买一个股票或卖出一个股票或者什么都不做，一天只能干一件事。

那么为了搞个大事情，你希望赚的钱最多，那么你最多能获得多少钱呢？ (注意到最终手上的股票不能算钱, 并且你可以暂时亏损)

输入格式：

第一行一个整数 $n$，表示天数

接下来一行 $n$ 个数，表示每天股票的价格

输出格式：

一行一个数，表示最大能挣的钱

输入1：

9
10 5 4 7 9 12 6 2 10

输出1：

20

输入2：

20
3 1 8 1 7 9 5 6 5 3 5 8 2 7 9 3 2 3 8 4

输出2：

41

数据范围：

打包测试

测试包 1: $n \leq 15,~55$ 分

测试包 2: $n \leq 100,~a_i \leq 100 ,~10$分

测试包 3: $n \leq 5000 ,~20$分

测试包 4: $a_i \leq a_{i+1} ,~10$分

测试包 5: 无特殊限制 $5$ 分

对于 $100\%$ 的数据 $1 \leq a_i \leq 10^6,1 \leq n \leq 3\times 10^5$

题解：

好可怕的贪心！QAQ

样例一某种程度上提示了我们，如何选择更好的一天卖出很重要

而很多时候我们只是不知道之后还有更好的机会卖出，显然反悔型贪心。

倒着考虑每天，维护一个可以卖的时候的大根堆

对于每个数 $a_i$ ，如果它比堆顶小，则把堆顶 $a_k$ 踢掉，代表在这一天买了股票，在堆顶卖出

并且， $a_i$ 也要入堆，因为不一定这一天买是最优的

当 $a_i$ 入堆以后，在未来某次决策中

如果有一个数 $a_j$ 加入，并踢掉了 $a_i$

这就等价于在 $a_j$ 买入， $a_i$ 卖出，再在 $a_i$ 买入，再在之前那个 $a_k$ 卖出

加粗的部分在实际决策时是不会做的，这个决策最后就等价于 $a_j$ 买 $a_k$ 卖

值得注意的时，此时我们还要把 $a_i$ 入堆，因为它也可以卖东西了（这个在代码里用 $\text{vis}$ 数组标记）

然后这题就搞定了，好难啊

时间复杂度 $O(n\log n)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
#include <bitset>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(3e5+15)

bitset<N> vis;
int n,res,a[N];
struct cmp{bool operator()(int x,int y){return a[x]<a[y];}};
priority_queue<int,vector<int>,cmp> q;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    for(int i=n; i>=1; i--)
    {
        if(!q.empty())
        {
            int x=q.top();
            if(a[i]<a[x])
            {
                q.pop(); res+=a[x]-a[i];
                q.push(i); vis[i]=1;
                if(vis[x]) vis[x]=0,q.push(x);
            }else q.push(i);
        }else q.push(i);
    }
    cout << res << '\n';
    return 0;
}