1 条题解

  • 0
    @ 2022-8-28 9:26:20
    #include<bits/stdc++.h>
    using namespace std;
    #define db double
    #define eps 1e-9//一定要注意精度
    #define inf 1e9
    const int N=100005;
    int n,rt,sc,f[N],son[N][2];
    db dp[N],A[N],B[N],R[N],lk[N],rk[N],X[N],Y[N];//lk:凸包点x左线斜率,rk:右线斜率
    int is(int x) {return son[f[x]][1]==x;}
    void spin(int x,int &mb) {
        int fa=f[x],g=f[fa],t=is(x);
        if(fa==mb) mb=x;
        else son[g][is(fa)]=x;
        f[fa]=x,f[x]=g,f[son[x][t^1]]=fa;
        son[fa][t]=son[x][t^1],son[x][t^1]=fa;
    }
    void splay(int x,int &mb) {
        while(x!=mb) {
            if(f[x]!=mb) {
                if(is(x)^is(f[x])) spin(x,mb);
                else spin(f[x],mb);
            }
            spin(x,mb);
        }
    }
    int find(int x,db num) {//寻找最优解
        if(!x) return 0;
        if(lk[x]+eps>=num&&rk[x]<=num+eps) return x;
        else if(lk[x]<num+eps) return find(son[x][0],num);
        else return find(son[x][1],num);
    }
    db getk(int a,int b) {//获得斜率
        if(X[a]-X[b]<eps&&X[a]-X[b]>-eps) return -inf;
        return (Y[b]-Y[a])/(X[b]-X[a]);
    }
    int pre(int x) {//寻找左边最后一个与x可以构成凸包的点
        int y=son[x][0],re=y;
        while(y) {
            if(lk[y]+eps>=getk(y,x)) re=y,y=son[y][1];
            else y=son[y][0];
        }
        return re;
    }
    int nxt(int x) {//寻找右边第一个与x可以构成凸包的点
        int y=son[x][1],re=y;
        while(y) {
            if(rk[y]<=getk(x,y)+eps) re=y,y=son[y][0];
            else y=son[y][1];
        }
        return re;
    }
    void newjd(int x) {
        splay(x,rt);
        if(son[x][0]) {
            int kl=pre(x);
            splay(kl,son[x][0]),son[kl][1]=0;
            lk[x]=rk[kl]=getk(kl,x);
        }
        else lk[x]=inf;//请勿往左
        if(son[x][1]) {
            int kl=nxt(x);
            splay(kl,son[x][1]),son[kl][0]=0;
            rk[x]=lk[kl]=getk(x,kl);
        }
        else rk[x]=-inf;//请勿往右
        if(lk[x]<=rk[x]+eps) {//在原凸包内部,直接删除该点
            rt=son[x][0],son[rt][1]=son[x][1],f[son[x][1]]=rt,f[rt]=0;
            lk[rt]=rk[son[rt][1]]=getk(rt,son[rt][1]);
        }
    }
    void ins(int &x,int las,int bh) {
        if(!x) {x=bh,f[x]=las;return;}
        if(X[bh]<=X[x]+eps) ins(son[x][0],x,bh);
        else ins(son[x][1],x,bh);
    }
    int main()
    {
        scanf("%d%lf",&n,&dp[0]);
        for(int i=1;i<=n;++i) {
            scanf("%lf%lf%lf",&A[i],&B[i],&R[i]);
            int j=find(rt,-A[i]/B[i]);
            dp[i]=max(dp[i-1],X[j]*A[i]+Y[j]*B[i]);
            Y[i]=dp[i]/(A[i]*R[i]+B[i]),X[i]=Y[i]*R[i];
            ins(rt,0,i),newjd(i);
        }
        printf("%.3lf\n",dp[n]);
        return 0;
    }
    
  • 1

信息

ID
1492
时间
1000ms
内存
256MiB
难度
5
标签
(无)
递交数
27
已通过
13
上传者