[bzoj5343][loj2555]: [Ctsc2018]混合果汁 （二分答案+主席树）

www.cnblogs.com/shaokele/

题目地址：　　[loj2555]: [Ctsc2018]混合果汁

题目大意： 　　题目很简洁了：）

　　

题解：

　　二分答案，用主席树维护贪心操作

　　

　　先按 \(d\) 排序，二分 \(ans\)

　　

　　主席树操作判断是否符合

　　

　　细节注意

　　

AC代码

#include <cstdio> 
#include <algorithm>
#define ll long long
using namespace std;
const int N=1e5+5,M=1800005;
int n,Q,sz,mxd,mxp;
int ls[M],rs[M],root[M];
ll g,L;
ll s[N],sum[M],val[M];
inline ll read(){   
    ll x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct node{
        int d,p,l;
}A[N];
bool operator < (const node &a,const node &b){
        return a.d<b.d; 
}
void insert(int l,int r,int &u,int pre,int p,int L){
    u=++sz;
    sum[u]=sum[pre];val[u]=val[pre];
    ls[u]=ls[pre];rs[u]=rs[pre];
    sum[u]+=L;val[u]+=1ll*p*L;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(p<=mid)insert(l,mid,ls[u],ls[pre],p,L);
    else insert(mid+1,r,rs[u],rs[pre],p,L);
}
ll ask(int l,int r,int u,int pre,ll L){
    if(!u)return 0;
    if(l==r)return L*l;
    int mid=(l+r)>>1;
    ll tmp=sum[ls[u]]-sum[ls[pre]];
    if(tmp>=L)return ask(l,mid,ls[u],ls[pre],L);
    else return val[ls[u]]-val[ls[pre]]+ask(mid+1,r,rs[u],rs[pre],L-tmp);
}
bool check(int mid,ll g,ll L){
    int pre=lower_bound(A+1,A+n+1,(node){mid,0,0})-A-1;
    if(s[n]-s[pre]<L)return 0;
    else return ask(1,mxp,root[n],root[pre],L)<=g;
}
int main(){
    n=read(),Q=read();
    for(int i=1;i<=n;i++){
        A[i].d=read(),A[i].p=read(),A[i].l=read();
        mxd=max(mxd,A[i].d);
        mxp=max(mxp,A[i].p);
    }
    sort(A+1,A+n+1);
    for(int i=1;i<=n;i++)
        s[i]=s[i-1]+A[i].l;
    for(int i=1;i<=n;i++)
        insert(1,mxp,root[i],root[i-1],A[i].p,A[i].l);
    while(Q--){
        g=read(),L=read();
        int l=1,r=mxd,ans=-1;
        while(l<=r){
            int mid=(l+r)/2;
            if(check(mid,g,L)){
                ans=mid;
                l=mid+1;
            }else r=mid-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}
           

转载于:https://www.cnblogs.com/shaokele/p/9109071.html