https://www.luogu.org/problemnew/show/P4602
https://www.lydsy.com/JudgeOnline/problem.php?id=5343
比较简单……前提是不会把题看成“果汁美味度=美味度之和”。
这样一来我们先对美味度排序，然后二分答案，就可以知道我们只可以取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/ +
+++++++++++++++++++++++++++++++++++++++++++