自动搬运

查看原文

来自洛谷，原作者为

	xiezheyuan 明明我已昼夜无间踏尽前路/梦想中的彼岸为何还未到/明明我已奋力无间/天天上路/我不死也为活更好/快要到终点才能知道/又再回到起点重头上路

搬运于2025-08-24 23:00:47，当前版本为作者最后更新于2024-07-12 08:17:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

你发现如果要考虑每个点被挖了多少格，那么至少需要 $O(n^2)$ 的时间复杂度，难以通过本题。

我们转而考虑挖的深度的差分数组。按照题意，差分数组的每一项只可能是 $1,-1,0$。我们不妨将 $1$ 看成一个左括号，$-1$ 的前一个位置看成一个右括号，$0$ 要么是不打括号，要么是一个右括号和一个左括号。

那么这些括号必须匹配。因为假如括号不匹配，那么会出现以下两种情况：

• 左括号不匹配，则最后一个位置会出现不合法的情况。
• 右括号不匹配，则会出现一个位置挖了负数格的情况。

然后对 $a$ 求前缀和，就转换成了经典问题。参考 CF865D Buy Low Sell High。

但是这道题剩余部分虽然和 Buy Low Sell High 一样，但是思考起来更容易。我们发现可以打左括号的地方一定可以打右括号，要不然的话括号匹配就会出锅。所以我们维护一个堆，每次将合法的左括号丢到堆里面去，然后看这里打一个右括号是否更优即可。

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

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2.5e5 + 5;
int n, ans, qzh[N], a[N];
priority_queue<int, vector<int>, greater<int> > pq;

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=n;i++) qzh[i] = qzh[i - 1] + a[i];
    for(int i=1;i<=n;i++){
        pq.push(qzh[i - 1]);
        if(qzh[i] - pq.top() > 0){
            ans += qzh[i] - pq.top();
            pq.pop();
            pq.push(qzh[i]);
        }
    }
    cout << ans << '\n';
    return 0;
}

// Written by xiezheyuan