首页 > 其他 > 详细

Codeforces Round #318 (Div. 2) D Bear and Blocks

时间:2015-08-30 11:07:58      阅读:335      评论:0      收藏:0      [点我收藏+]

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

当k == min(hi-j+j,hi+j+j)时hi会变成0,因为min具有传递性,那么可以左右分开来考虑,hi-j+j化一下就是hi-j-(i-j)+i,其中后面i和j无关,所以只要找出前面最小的hi-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\n",ans);
    return 0;
}

 

Codeforces Round #318 (Div. 2) D Bear and Blocks

原文:http://www.cnblogs.com/jerryRey/p/4770393.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!