题解：P10736 [SEERC2020] Archeologists

xiezheyuan · 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