这题在今年CTSC中属于非常可做的题吧...
首先注意题中询问的美味度为最小值而不是求和，
所以自然而然能想到二分美味度下界，
然后对于美味度大于下届的这些果汁中随便选，凑出g[i]，发现选谁都是等价的，所以直接选便宜的，相当于选前g[i]便宜的，与L[i]比较大小
然后求前k小的和显然可以用主席树做，当然我的主席树可能比较垃圾....
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; const int N=1e5+5; ll n,m,maxn,tcnt,maxp; ll u,v; ll rt[20*N]; struct tree { ll l,r; ll sum,cnt; }t[20*N]; struct juice { ll d,p,l; inline void read() { scanf("%lld%lld%lld",&d,&p,&l); maxn=max(maxn,d); maxp=max(maxp,p); } friend inline bool operator < (const juice &a,const juice &b) { return a.d<b.d; } }a[N]; void insert(ll y,ll &x,ll l,ll r,ll p,ll w) { t[x=++tcnt]=t[y]; t[x].cnt+=w; t[x].sum+=w*p; ll mid=l+r>>1; if(l==r) return ; if(p<=mid) insert(t[y].l,t[x].l,l,mid,p,w); else insert(t[y].r,t[x].r,mid+1,r,p,w); } bool query(ll y,ll x,ll l,ll r,ll u,ll v) { ll delta1=t[t[x].l].cnt-t[t[y].l].cnt,delta2=t[t[x].l].sum-t[t[y].l].sum; //printf("%d %d %lld %lld ",l,r,delta1,delta2); if(l==r) { ll lft1=t[x].cnt-t[y].cnt,lft2=t[x].sum-t[y].sum; if(lft1<v) return 0; return u>=(lft2/lft1)*v; } ll mid=l+r>>1; if(delta1>=v) { if(u>=delta2) return 1; return query(t[y].l,t[x].l,l,mid,u,v); } else { if(u<delta2) return 0; return query(t[y].r,t[x].r,mid+1,r,u-delta2,v-delta1); } } bool check(ll x) { ll l=1,r=n; while(l<r) { ll mid=l+r>>1; if(a[mid].d>=x) r=mid; else l=mid+1; } //printf ("%d:%d-%lld-%lld ",x,l,u,v); return query(rt[l-1],rt[n],1,maxp,u,v); } ll solve() { ll l=1,r=maxn; if(!check(1)) return -1; while(l<r) { ll mid=l+r+1>>1; if(check(mid)) l=mid; else r=mid-1; } return l; } int main() { scanf("%lld%lld",&n,&m); for(ll i=1;i<=n;i++) a[i].read(); sort(a+1,a+n+1); for(ll i=1;i<=n;i++) insert(rt[i-1],rt[i],1,maxp,a[i].p,a[i].l); ll x,y; for(ll i=1;i<=m;i++) { scanf("%lld%lld",&u,&v); printf("%lld ",solve()); } return 0; }