题解 CF955E 【Icicles】
VenusM1nT
2020-11-22 20:10:47
考虑在 $T$ 点释放声波，那么第 $i$ 个位置的冰锥会在 $f_T(i)=a_i+|T-i|$ 时刻之后落地，若存在最小的 $j$ 使得 $f_T(j)<j$，那么 Krakozyabra 会在 $j$ 时刻被挡住，然后再等到左侧冰锥落下。考虑到后面可能有冰锥更早落下，可以得到答案为
$$\max\{\min_{1\leq i<j}\{f_T(i)\},\min_{j\leq i\leq n}\{f_T(i)\}\}$$
此时复杂度为 $\text{O}(n^2)$，考虑优化。将 $f_T$ 中的绝对值拆掉，分别为 $f_T(i)=a_i+T-i\ (i\leq T)$，$f_T(i)=a_i-T+i\ (i>T)$，用两个数组 $\text{pre,\ suf}$ 存储。考虑转化 $f_T(i)<i$ 这个不等式，根据前面提到的拆绝对值，若 $i\leq T$，即为 $T<i\times 2-a_i$；若 $i>T$，即为 $a_i<T$。至此，可以通过枚举 $T$，二分 $i$，配合任意一种 rmq 算法得到答案。
```cpp
#include<bits/stdc++.h>
#define N 100000
#define reg register
#define inl inline
#define inf 1e9
using namespace std;
int n,a[N+5],_[N+5],minx[N+5][25],pre[N+5][25],suf[N+5][25];
inl int Query(reg int l,reg int r)
{
if(l>r) return inf;
reg int k=_[r-l+1];
return min(minx[l][k],minx[r-(1<<k)+1][k]);
}
inl int QryP(reg int l,reg int r)
{
if(l>r) return inf;
reg int k=_[r-l+1];
return min(pre[l][k],pre[r-(1<<k)+1][k]);
}
inl int QryS(reg int l,reg int r)
{
if(l>r) return inf;
reg int k=_[r-l+1];
return min(suf[l][k],suf[r-(1<<k)+1][k]);
}
int main()
{
scanf("%d",&n);
for(reg int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
minx[i][0]=a[i];
pre[i][0]=a[i]-i;
suf[i][0]=a[i]+i;
}
for(reg int i=2;i<=n;i++) _[i]=_[i>>1]+1;
for(reg int j=1;j<=20;j++)
{
for(reg int i=1;i<=n-(1<<j)+1;i++)
{
minx[i][j]=min(minx[i][j-1],minx[i+(1<<(j-1))][j-1]);
pre[i][j]=min(pre[i][j-1],pre[i+(1<<(j-1))][j-1]);
suf[i][j]=min(suf[i][j-1],suf[i+(1<<(j-1))][j-1]);
}
}
reg int now=1,ans=inf;
for(reg int i=1;i<=n;i++)
{
while(now<=i && now*2-a[now]<=i) now++;
reg int x,y,pos=-1;
if(now<=i) pos=now;
else
{
reg int l=i,r=n;
while(l<=r)
{
reg int mid=(l+r)>>1;
if(Query(i,mid)<i)
{
pos=mid;
r=mid-1;
}
else l=mid+1;
}
if(!~pos) continue;
}
if(pos<=i)
{
x=QryP(1,pos-1)+i;
y=min(QryP(pos,i)+i,QryS(i+1,n)-i);
}
else
{
x=QryS(pos,n)-i;
y=min(QryP(1,i)+i,QryS(i+1,pos-1)-i);
}
ans=min(ans,max(x,y));
}
printf("%d\n",ans>=inf/2?-1:ans);
return 0;
}
```