题解 P3571 【[POI2014]SUP-Supercomputer】

· · 题解

洛谷上有两类题目，标签难度远远高于真实难度和标签难度远远低于真实难度。 这题属于前者。

ans=max(\lceil \frac{i}{sum[i+1]/k} \rceil)

这个暴力求是 \Theta(n*q) 的。

怎么优化？？？

里面有个除号，拿出来 当然，先把这个向上整除忽略一下，等下会讨论到。

ans \times k=max(i \times k + sum[i+1]);

k是一个常数

这个可以看出是线性规划

y=k \times x+z y=sum[i+1]x=i z=-ans \times k

要最大化ans 那么就要最小化z

很显然造一个上凸包然后把k排序一下，用个单调队列扫过去就可以了。

struct P2{

    ll Chk(int x,int K){
        return 1ll*sum[x+1]+K*x;
    }
    int DP(int j,int K){
        return j+ceil(1.0*sum[j+1]/K);
    }
    void Do(){
        int x;
        d=-1;
        for(int i=1;i<=Q;i++){
            scanf("%d",&k[i]);
            A[i]=(node){k[i],i};
        }
        sort(A+1,A+Q+1);
        for(int i=2;i<=n;i++){
            scanf("%d",&x);
            E[x].pb(i);
        }
        dfs(1,1);
        for(int i=d;i>=1;i--) sum[i]+=sum[i+1];

        int head=1,tail=0;
        for(int i=1;i<=d;i++){
            while(tail-head>=1&&1.0*(sum[q[tail]+1]-sum[q[tail-1]+1])*(i-q[tail])<1.0*(sum[i+1]-sum[q[tail]+1])*(q[tail]-q[tail-1])) tail--;
            q[++tail]=i;
        }

        for(int i=1;i<=Q;i++){
            while(head<tail&&Chk(q[head],A[i].k)<=Chk(q[head+1],A[i].k)) head++;
            ans[A[i].id]=DP(q[head],A[i].k);
        }
        for(int i=1;i<=Q;i++){
            printf("%d",ans[i]);
            if(i!=Q) printf(" ");
        }
    }
}Solve2;