BZOJ2792: [Poi2012]Well【二分+two-pointer】

2792: [Poi2012]Well

【题目描述】

传送门

【题解】

二分答案,先不考虑0的情况对这个序列进行修正,然后枚举0所在的位置,找到需要更新的左右边界,可以用two-pointer。

代码如下

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int MAXN=1000005;
int n,K,a[MAXN],b[MAXN];LL m,Sum[MAXN];
#include<cctype>
char nc(){
    static char buf[100000],*L=buf,*R=buf;
    return (L==R&&(R=(L=buf)+fread(buf,1,100000,stdin)),L==R)?EOF:*L++;
}
LL read(){
    LL ret=0;char ch=nc();bool f=1;
    for(;!isdigit(ch);ch=nc()) f^=!(ch^'-');
    for(; isdigit(ch);ch=nc()) ret=(ret<<1)+(ret<<3)+ch-48;
    return f?ret:-ret;
}
LL Cal(LL x,LL y,int L){return (x+y)*L/2;}
bool check(int D){
    LL Ned=0;
    for(int i=1;i<=n;i++) b[i]=a[i];
    for(int i=2;i<=n;i++) b[i]=min(b[i],b[i-1]+D);
    for(int i=n-1;i;i--) b[i]=min(b[i],b[i+1]+D);
    for(int i=1;i<=n;i++) Sum[i]=Sum[i-1]+b[i],Ned+=(a[i]-b[i]);
    for(int i=1,l=1,r=1;i<=n;i++){
        while(l<i&&b[l]<=(LL)D*(i-l)) l++;
        while(r+1<=n&&b[r+1]>(LL)D*(r-i+1)) r++;
        LL Add=(Sum[r]-Sum[l-1])-Cal(0ll,(LL)D*(i-l),i-l+1)-Cal(0ll,(LL)D*(r-i),r-i+1);
        if(Add+Ned<=m){K=i;return 1;}
    }
    return 0;
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    int Ans=0;
    for(int L=0,R=1e9,mid=(R-L>>1)+L;L<=R;mid=(R-L>>1)+L)
    if(check(mid)) Ans=mid,R=mid-1;else L=mid+1;
    check(Ans);
    printf("%d %d\n",K,Ans);
    return 0;
}

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部