洛谷4602 [CTSC2018]混合果汁

Luogu

分析

显然答案是可以二分的,那么只需要判断用美味度 $\geq d$ 的果汁能不能在不超过 $g$ 元的情况下凑出 $L$ 升即可。

考虑我们一定优先买便宜的果汁,因此可以维护一棵以价格为下标的权值线段树,那么在线段树上二分即可判断是否可行。

现在还有一个美味度 $\geq d$ 的限制,于是只要按 $d$ 从大到小插入一棵主席树就好了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,m;

struct juice { int d,p,l; } a[N];
bool operator <(juice a,juice b) { return a.d>b.d; }

int rt[N],tot=0;
struct node { int ls,rs,sump,suml; } t[N*30];
inline void pushup(int o) {
    t[o].sump=t[t[o].ls].sump+t[t[o].rs].sump;
    t[o].suml=t[t[o].ls].suml+t[t[o].rs].suml;
}
inline void modify(int& p,int q,int l,int r,int p_,int l_) {
    t[p=++tot]=t[q];
    if (l==r) { t[p].sump+=p_*l_,t[p].suml+=l_; return; }
    int mid=(l+r)>>1;
    if (p_<=mid) modify(t[p].ls,t[q].ls,l,mid,p_,l_);
    else modify(t[p].rs,t[q].rs,mid+1,r,p_,l_);
    pushup(p);
}
inline int query(int o,int l,int r,int g,int L) {
    if (L>t[o].suml) return 0;
    if (g>t[o].sump) return 1;
    if (l==r) return l*L<=g;
    int mid=(l+r)>>1,lsump=t[t[o].ls].sump,lsuml=t[t[o].ls].suml;
    if (L<=lsuml) return query(t[o].ls,l,mid,g,L);
    else return query(t[o].rs,mid+1,r,g-lsump,L-lsuml);
}

signed main() {
    n=read(),m=read(); int maxp=0;
    for (re int i=1;i<=n;++i) {
        a[i].d=read(),a[i].p=read(),a[i].l=read();
        maxp=max(maxp,a[i].p);
    }            
    sort(a+1,a+n+1);
    for (re int i=1;i<=n;++i)
        modify(rt[i],rt[i-1],1,maxp,a[i].p,a[i].l);
    while (m--) {
        int g=read(),L=read();
        if (!query(rt[n],1,maxp,g,L)) puts("-1");
        else {
            int l=1,r=n;
            while (l<r) {
                int mid=(l+r)>>1;
                if (query(rt[mid],1,maxp,g,L)) r=mid;
                else l=mid+1;
            }
            printf("%lld\n",a[l].d);
        }
    }
    return 0;
}
最后修改:2019 年 10 月 17 日 04 : 56 PM

发表评论