Educational Codeforces Round 158 (Rated for Div. 2)D

题意：

思路：维护前后缀最大值（选某个点作为起点的时候只考虑一侧的最大值），因为只能连续清除，那么考虑枚举i，最大值只能出现在3种情况：

1.本身

2.把i以及左侧清理完，加上suf[i+1]，最大值产生在右侧

3.把i以及右侧清理完，加上pre[i-1]，最大值产生在左侧

#include<bits/stdc++.h> #define int long long #define fi first #define se second #define endl '\n' using namespace std; typedef pair<int,int> pii; const int N=1e6+10; const int mod=998244353; vector<int>pm; int judge[N],nm[N],inv[N]; int Log2[N]; int kmi(int a,int b){ int res=1; while(b){ if(b&1) res=res*a%mod; a=a*a%mod; b>>=1; } return res; } void init(){ nm[0]=inv[0]=1; for(int i=1;i<=1e6;i++){ nm[i]=nm[i-1]*i%mod; inv[i]=kmi(nm[i],mod-2); } } void euler(int n){ judge[1]=1; for(int i=2;i<=n;i++){ if(!judge[i]){ pm.push_back(i); } for(int j=0;pm[j]*i<=n;j++){ judge[pm[j]*i]=1; if(i%pm[j]==0) break; } } } int C(int a,int b){ return nm[a]*inv[a-b]%mod*inv[b]%mod; } // struct nod{ // int p,val; // bool operator<(const nod &b)const{ // return val>b.val; // } // }; //维护单边最大值，枚举i，假设删除掉i以及左边所有元素 void solve(){ int n;cin>>n; vector<int>a(n+10),pre(n+10),suf(n+10); for(int i=1;i<=n;i++) cin>>a[i]; int ans=1e18; for(int i=1;i<=n;i++){ pre[i]=max(pre[i-1]+1,a[i]); } for(int i=n;i>=1;i--){ suf[i]=max(suf[i+1]+1,a[i]); } for(int i=1;i<=n;i++){ int mx=max({a[i],suf[i+1]+i-1,pre[i-1]+n-i+1}); ans=min(ans,mx); } cout<<ans; } signed main(){ ios::sync_with_stdio(0);cin.tie(0); // for(int i=2;i<=1e6;i++){ // Log2[i]=Log2[i/2]+1; // } int T=1;//cin>>T; while(T--) solve(); return 0; }