Gym - 100851L:Landscape Improved (二分+单调性)

题意： 一个宽度为N的网格图，i上有h[i]高的方块。现在你有W个方块，问怎么放使得最终的最高点最高。

　　当一个格子的下方，左下方和右下方都有方块那么久可以把方块放到这个格子上。最左端和最右端不能放方块。

　　（N<=100000,W<=10¹⁸,h[i]<=10⁹）

思路：显然是二分，对于二分的高度Mid，我们验证是否有i能够达到这个高度。我们已知需要填充的部分是从i向两旁延伸，知道左边满足i-pos>=Mid-h[pos]

右边满足pos-i>=Mid-h[pos]，我们需要对于每个i找到Lpos和Rpos，然后用前缀和O(1)算出需要的方块。

现在的关键就是对于Mid，O(N)内预处理得到L和R数组：对于pos，它影响的范围是pos+Mid-h[pos]及其以后，那么记录下L[pos+Mid-h[pos]]=pos，然后扫描更新一遍最大值即可；R数组同理。

（emmm，我个zz，果然还是太弱。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=;

int N,L[maxn],R[maxn]; ll sum[maxn],h[maxn],W;

bool check(ll Mid)

{

    int i;

    for(i=;i<=N+;i++) L[i]=,R[i]=N+;

    for(i=;i<=N;i++) if(i+Mid-h[i]<=N&&i+Mid-h[i]>=i) L[i+Mid-h[i]]=i;

    for(i=N;i>=;i--) if(i-Mid+h[i]>=&&i-Mid+h[i]<=i) R[i-Mid+h[i]]=i; //方向不能反，因为要最近的

    for(i=;i<=N;i++) L[i]=max(L[i],L[i-]);

    for(i=N;i>=;i--) R[i]=min(R[i],R[i+]);

    for(i=;i<=N;i++){

        if(R[i]==N+||L[i]==) continue;

        ll res=;

        res+=1LL*(Mid+Mid-(i-L[i])+)*(i-L[i])/;

        res+=1LL*(Mid-+Mid--(R[i]-i-)+)*(R[i]-i-)/;

        res-=sum[R[i]-]-sum[L[i]];

        if(res<=W) return true;

    }

    return false;

}

int main()

{

    scanf("%d%I64d",&N,&W);

    ll l=,r=,Mid,ans;

    for(int i=;i<=N;i++) scanf("%I64d",&h[i]),l=max(l,h[i]),sum[i]=sum[i-]+h[i];

    while(l<=r){

        Mid=(l+r)/;

        if(check(Mid)) l=Mid+,ans=Mid;

        else r=Mid-;

    }

    printf("%I64d\n",ans);

    return ;

}

巴特西

Gym - 100851L:Landscape Improved (二分+单调性)

最新文章

热门文章