BZOJ5343[Ctsc2018]混合果汁——主席树+二分答案-白红宇

BZOJ5343[Ctsc2018]混合果汁——主席树+二分答案

阅读量：6863 次

发布时间：2019-06-26

本文共 1220 字，大约阅读时间需要 4 分钟。

题目链接：

显然如果美味度高的合法那么美味度低的一定合法，因为美味度低的可选方案包含美味度高的可选方案。

那么我们二分一个美味度作为答案然后考虑如何验证？

选择时显然要贪心的先选单价低的果汁。

那么我们按美味度从大到小将每种果汁排序，然后对于每种果汁建立一个版本的主席树，主席树维护的权值是果汁单价。

每次验证时在对应版本主席树中查找，如果左子树中总体积大于L则递归左子树，否则将答案加上左子树所有果汁的总价然后递归右子树。

#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #define ll long longusing namespace std;struct miku{ int d; ll g,l;}s[100010];int cnt;int n,m,q;ll G,L;int ls[2000010];int rs[2000010];ll sum[2000010];ll num[2000010];int root[100010];ll h[100010];bool cmp(miku a,miku b){ if(a.d!=b.d) { return a.d>b.d; } return a.g
                
                 >1; if(x<=mid) { updata(ls[rt],ls[pre],l,mid,x,val,lim); } else { updata(rs[rt],rs[pre],mid+1,r,x,val,lim); }}ll query(int rt,int l,int r,ll k){ if(l==r) { return k*h[l]; } int mid=(l+r)>>1; if(num[ls[rt]]>=k) { return query(ls[rt],l,mid,k); } else { return sum[ls[rt]]+query(rs[rt],mid+1,r,k-num[ls[rt]]); }}bool check(int x){ if(num[root[x]]
                 
                  >1; if(check(mid)==true) { ans=mid; r=mid-1; } else { l=mid+1; } } if(ans==-1) { printf("-1\n"); continue; } printf("%d\n",s[ans].d); }}

转载于:https://www.cnblogs.com/Khada-Jhin/p/10028956.html

你可能感兴趣的文章