自动搬运

查看原文

来自洛谷，原作者为

	kouylan 这人真的菜 | 已AFO

搬运于2025-08-24 22:01:50，当前版本为作者最后更新于2020-09-03 22:07:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解 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 愉快！