题解 P4602 【[CTSC2018]混合果汁】

· · 题解

题解 P4602 【[CTSC2018]混合果汁】

洛谷题面传送门

一眼就能看出，这道题可以二分答案。

假设二分出的果汁最小美味值是 m，则我们只要考虑美味值 d_i\geq m 的果汁即可。所以我们想到把果汁按照 d_i 排序，这样每次就不用一个一个枚举。

接下来我们就要想怎么 \mathrm{check} 就好了。贪心的想，我们就按照价格 p_i 从小往大取，肯定是最优的。

所以关键问题是价格，再看数据范围，只够我们再加一个 \mathrm{logn}，那我们就能想到根据价格建立权值线段树，又因为我们要查询的都是区间，把它优化成主席树，就会方便许多。

现在，我们想如何按照我们的贪心思路在主席树上查询。假设我们现在在节点 o 上，我们肯定优先先往左子树走，因为左子树对应的价格更小嘛。但我们还要保证果汁数量要 \geq L。所以，这个问题就有点类似于区间第 k 小的问题。如果左子树中的果汁数量 \gep L，我们就去左子树找；反之，我们要取完左子树的所有果汁，并把剩下的果汁带到右子树中找就行了。

因此，我们在主席树中就要存两个信息。一是对应区间的果汁数量，而是对应区间果汁全取的价格。

最后，贪心取出的价格如果 \leq g，并且果汁数量 \geq L，就是合法的。

下面是 AC 代码

/*
luogu P4602
*/
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define mid (l+r>>1)

const int N = 1e5;

int n,q,ans;
struct juice{
    int d,p,m;
    bool operator < (const juice b) const
    {
        return d>b.d;
    }
}a[100005];
int cnt,root[100005];
struct hjtree{
    int l,r,s,sum;
}t[100005<<6];

void insert(int &o,int pre,int l,int r,int x,int v)
{
    o = ++cnt;
    t[o] = t[pre];
    t[o].s += v, t[o].sum += x*v;
    if(l==x && r==x)
        return;
    if(x<=mid)
        insert(t[o].l,t[pre].l,l,mid,x,v);
    else
        insert(t[o].r,t[pre].r,mid+1,r,x,v);
}

int query(int o,int l,int r,int k)
{
    if(l==r)
        return l*k;
    if(t[t[o].l].s>=k)
        return query(t[o].l,l,mid,k);
    else
        return t[t[o].l].sum+query(t[o].r,mid+1,r,k-t[t[o].l].s);
}

signed main()
{
    cin>>n>>q;
    for(int i=1;i<=n;cin>>a[i].d>>a[i].p>>a[i].m,i++);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
        insert(root[i],root[i-1],1,N,a[i].p,a[i].m);
    while(q--)
    {
        int g,lim;
        cin>>g>>lim;
        ans = -1;
        int l=1,r=n;
        while(l<=r)
        {
            int res=query(root[mid],1,N,lim);
            if(res<=g && t[root[mid]].s>=lim)
                ans = mid, r = mid-1;
            else
                l = mid+1;
        }
        cout<<(ans==-1 ? -1 : a[ans].d)<<endl;
    }
}

祝大家 AC 愉快！