题解：AT_abc443_d [ABC443D] Pawn Line

wyyinput · 2026-02-01 10:50:36 · 题解

做法比较好猜，就是左右扫一遍。

:::info[为什么只扫一遍是对的？]{open} 看似一个点的位置可能会被多个点影响，但这一定不可能。

我们可以把每一个点往左下方、右下方各做一条直线，那最后每个点只会被最高的直线影响。所以一个点只会被刚好一个点限制。 :::

对每个点维护两条直线显然不现实。可以动态维护每个位置的最高高度。如果上一个位置的高度是 k，则这个位置就是 \min(k+1,R_i)。代码很简单。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define fi first
#define se second
#define gtc getchar
#define ptc putchar
using namespace std;
const int N=3e5+5;
int t;
int n;
int a[N];
int maxn[N];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",a+i);
            maxn[i]=a[i];
        }
        int p=a[1];
        for(int i=2;i<=n;i++){
            p=min(p+1,a[i]);
            maxn[i]=min(p,maxn[i]);
        }
        p=a[n];
        for(int i=n-1;i;i--){
            p=min(p+1,a[i]);
            maxn[i]=min(p,maxn[i]);
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            ans+=a[i]-maxn[i];
        }
        printf("%lld\n",ans);
    }
    return 0;
}

AC 记录。