Codeforces Round #318 (Div. 2) D Bear and Blocks （数学）

不难发现在一次操作以后，h_i=min(h_i-1,h_i-1,h_i+1)，迭代这个式子得到k次操作以后h_i=min(h_i-j-(k-j),h_i-k,h_i+j-(k-j)),j = 1,2,3...

当k == min(h_i-j+j,h_i+j+j)时hi会变成0，因为min具有传递性，那么可以左右分开来考虑，h_i-j+j化一下就是h_i-j-(i-j)+i，其中后面i和j无关，所以只要找出前面最小的h_i-i

对于右边的类似处理，最后再扫一遍，得出最大的一个k就是答案。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+2;
int n;
int h[maxn];
int k[maxn];

int main()
{
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",h+i);

    int cnt = 0;
    for(int i = 1; i <= n; i++){
       cnt = min(cnt,h[i]-i);
       k[i] = i + cnt;
    }
    cnt = n+1;
    for(int i = n; i >= 1; i--){
        cnt = min(cnt,h[i]+i);
        k[i] = min(k[i],cnt-i);
    }
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = max(ans,k[i]);
    }
    printf("%d
",ans);
    return 0;
}