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 ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/ +

+++++++++++++++++++++++++++++++++++++++++++

巴特西

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

最新文章

热门文章