BZOJ5343 & 洛谷4602 & LOJ2555：[CTSC2018]混合果汁——题解

小 R 热衷于做黑暗料理，尤其是混合果汁。

商店里有 n 种果汁，编号为 0,1,2,…,n−1。i 号果汁的美味度是 di，每升价格为 pi。小 R 在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中，i 号果汁最多只能添加 li 升。

现在有 m 个小朋友过来找小 R 要混合果汁喝，他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中，第 j 个小朋友希望他得到的混合果汁总价格不大于 gj，体积不小于 Lj。在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。

比较简单……前提是不会把题看成“果汁美味度=美味度之和”。

这样一来我们先对美味度排序，然后二分答案，就可以知道我们只可以取k~n的果汁，然后判断是否可行即可。

贪心的思路：我们按照p从小到大取果汁是最优的。

主席树显然可以胜任这个工作。

#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5+;
inline ll read(){
    ll X=,w=;char ch=;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
    return w?-X:X;
}
struct juice{
    int d,p,l;
}a[N];
struct tree{
    int l,r;
    ll v,s;
}tr[N*];
int n,m,t,pos[N],rt[N],pool;
inline bool cmp(juice a,juice b){
    return a.d<b.d;
}
inline void insert(int y,int &x,int l,int r,int p,int v){
    tr[x=++pool]=tr[y];
    tr[x].v+=(ll)p*v;tr[x].s+=v;
    if(l==r)return;
    int mid=(l+r)>>;
    if(p<=mid)insert(tr[y].l,tr[x].l,l,mid,p,v);
    else insert(tr[y].r,tr[x].r,mid+,r,p,v);
}
inline ll query(int nl,int nr,int l,int r,ll p){
    if(l==r)return min(p/l,tr[nr].s-tr[nl].s);
    ll delta=tr[tr[nr].l].v-tr[tr[nl].l].v;
    ll tmp=tr[tr[nr].l].s-tr[tr[nl].l].s;
    int mid=(l+r)>>;
    if(delta>p)return query(tr[nl].l,tr[nr].l,l,mid,p);
    else return tmp+query(tr[nl].r,tr[nr].r,mid+,r,p-delta);
}
ll G,L;
bool pan(int k){
    ll tmp=query(rt[k-],rt[n],,1e5,G);
    return tmp>=L;
}
ll solve(int l,int r){
    while(l<r){
    int mid=(l+r+)>>;
    if(pan(pos[mid]))l=mid;
    else r=mid-;
    }
    return pan(pos[l])?a[pos[l]].d:-;
}
int main(){
    n=read(),m=read();
    for(int i=;i<=n;i++)
    a[i].d=read(),a[i].p=read(),a[i].l=read();
    sort(a+,a+n+,cmp);
    for(int i=;i<=n;i++){
    if(a[pos[t]].d!=a[i].d)pos[++t]=i;
    insert(rt[i-],rt[i],,1e5,a[i].p,a[i].l);
    }
    for(int i=;i<=m;i++){
    G=read(),L=read();
    printf("%lld\n",solve(,t));
    }
    return ;
}