uoj #49. 【UR #3】铀仓库

http://uoj.ac/problem/49

这题二分答案可以做，同时存在另一个直接二分的解法。

考虑对每个点，二分能向左右延伸的最大半径，由于权值范围较大，不能O(1)查询向一侧走指定距离后到达的位置，又由于单调性，可以同时二分左右延伸的长度，如果可行考虑延长较短的一侧，否则缩短较长的一侧。

#include<cstdio>
typedef long long i64;
const int N=500007;
char buf[N*30],*ptr=buf-1;
template<class T>
T R(){
    T x=0;
    while(*ptr<48)++ptr;
    while(*ptr>47)x=x*10+*ptr++-48;
    return x;
}
int n,xs[N],as[N];
i64 t,s[N][2];
i64 cal(int l,int m,int r){
    return
    (s[r][1]-s[m][1])-(s[r][0]-s[m][0])*xs[m]-
    (s[m][1]-s[l-1][1])+(s[m][0]-s[l-1][0])*xs[m];
}
i64 min(i64 a,i64 b){return a<b?a:b;}
int main(){
    fread(buf,1,sizeof(buf),stdin);
    n=R<int>();
    t=R<i64>()/2;
    for(int i=1;i<=n;++i)xs[i]=R<int>();
    for(int i=1;i<=n;++i)as[i]=R<int>();
    for(int i=1;i<=n;++i){
        s[i][0]=s[i-1][0]+as[i];
        s[i][1]=s[i-1][1]+i64(as[i])*xs[i];
    }
    i64 ans=0;
    for(int i=1;i<=n;++i){
        int L1=1,R1=i,L2=i,R2=n,M1,M2;
        i64 v,cs;
        while(L1<R1&&L2<R2){
            M1=L1+R1>>1;
            M2=L2+R2+1>>1;
            v=cal(M1,i,M2);
            if(xs[i]-xs[M1]<xs[M2]-xs[i])v<=t?R1=M1:R2=M2-1;
            else v<=t?L2=M2:L1=M1+1;
        }
        while(L1<R1){
            M1=L1+R1>>1;
            v=cal(M1,i,L2);
            v<=t?R1=M1:L1=M1+1;
        }
        while(L2<R2){
            M2=L2+R2+1>>1;
            v=cal(L1,i,M2);
            v<=t?L2=M2:R2=M2-1;
        }
        v=t-cal(L1,i,L2);
        cs=s[L2][0]-s[L1-1][0];
        if(L1>1&&(L2==n||xs[i]-xs[L1-1]<xs[L2+1]-xs[i]))cs+=min(as[L1-1],v/(xs[i]-xs[L1-1]));
        else if(L2<n)cs+=min(as[L2+1],v/(xs[L2+1]-xs[i]));
        if(cs>ans)ans=cs;
    }
    printf("%lld
",ans);
    return 0;
}