loj2555&luogu4602 「CTSC2018」混合果汁

loj2555&luogu4602 「CTSC2018」混合果汁

​​ 题目描述

小 R 热衷于做黑暗料理，尤其是混合果汁。

商店里有

n

n 种果汁，编号为

0,1,\cdots,n-1

0,1,⋯,n−1 。

i

i 号果汁的美味度是

d_i

di ，每升价格为

p_i

pi 。小 R 在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中，

i

i 号果汁最多只能添加

l_i

li 升。

现在有

m

m 个小朋友过来找小 R 要混合果汁喝，他们都希望小 R 用商店里的果汁制作成一瓶混合果汁。其中，第

j

j 个小朋友希望他得到的混合果汁总价格不大于

g_j

gj ，体积不小于

L_j

Lj​ 。在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。 输入输出格式

输入格式：

输入第一行包含两个正整数

n, m

n,m ，表示果汁的种数和小朋友的数量。接下来

n

n 行，每行三个正整数

d_i, p_i, l_i

di,pi,li ，表示

i

i号果汁的美味度为

d_i

di ，每升价格为

p_i

pi ，在一瓶果汁中的添加上限为

l_i

li 。

接下来

m

m 行依次描述所有小朋友：每行两个数正整数

g_j, L_j

gj,Lj 描述一个小朋友，表示他最多能支付

g_j

gj 元钱，他想要至少

L_j

Lj 升果汁。

输出格式：

对于所有小朋友依次输出：对于每个小朋友，输出一行，包含一个整数，表示他能喝到的最美味的混合果汁的美味度。如果无法满足他的需求，则输出

-1

−1 。 输入输出样例

输入样例#1： 复制

3 4 1 3 5 2 1 3 3 2 5 6 3 5 3 10 10 20 10

输出样例#1： 复制

3 2 -1 1

说明

对于所有的测试数据，保证

n, m \le 100000

n,m≤100000 ，

1 \le d_i,p_i,l_i \le 10^5, 1 \le g_j, L_j \le 10^{18}

1≤di​,pi​,li​≤105,1≤gj​,Lj​≤1018 。 测试点编号

n=

n=

m=

m= 其他限制 1,2,3

10

10

10

10 无 4,5,6

500

500

500

500 无 7,8,9

5000

5000

5000

5000 无 10,11,12

100000

100000

100000

100000

p_i=1

pi​=1 13,14,15

100000

100000

100000

100000

l_i=1

li​=1 16,17,18,19,20

100000

100000

100000

100000 无

ctsc的水题..mdzz蒟蒻我部分分就写的正解 以为自己没能力就每写x

考虑二分一下这个d 然后看一下这个范围内花最小代价凑出L升果汁需要花的钱 看是否满足大于我能花的最多的钱 如果大于 说明我这个选择范围有点小 需要把可选择的d的范围进一步扩大才可以

#include#include#include#define ll long longusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline ll read(){ ll x=0,f=1;char ch=gc(); while(!isdigit(ch)) {if (ch=='-') f=-1;ch=gc();} while(isdigit(ch)) x=x*10+ch-'0',ch=gc(); return x*f;}const int N=100100;struct node{ int d,p,l;}jui[N];struct node1{ int left,right,v;ll sum,cnt;}tree[N*44];int q[N],nn,rt[N],n,m,num;ll ans1;inline bool cmp(const node &a,const node &b){return a.d>b.d;}inline void query(int x,int l,int r,ll p){ if (l==r){ans1+=(ll)tree[x].v*p;return;};int mid=l+r>>1; int ls=tree[x].left; if(p>tree[ls]-t){ ans1+=tree[ls].sum;query(tree[x].right,mid+1,r,p-tree[ls]-t); }else{ query(tree[x].left,l,mid,p); }}inline bool check(int md,ll lim,ll g){ ans1=0;if(tree[rt[md]]-t>1; if (p<=mid) insert1(tree[x].left,l,mid,p,v,lim); else insert1(tree[x].right,mid+1,r,p,v,lim);}ll sum;inline void gao(){ sort(jui+1,jui+n+1,cmp); //for (int i=1;i<=n;++i) printf("%d\n",jui[i].d); for (int i=1;i<=n;++i) q[i]=jui[i].p,sum+=jui[i].l; sort(q+1,q+n+1);nn=unique(q+1,q+n+1)-q-1; for (int i=1;i<=n;++i) { rt[i]=rt[i-1];int p=lower_bound(q+1,q+nn+1,jui[i].p)-q; insert1(rt[i],1,nn,p,jui[i].p,jui[i].l); } for (int owo=1;owo<=m;++owo){ ll g=read(),lim=read();if (lim>sum) {puts("-1");continue;} int l=1,r=n,ans; while(l<=r){ int mid=l+r>>1; if (check(mid,lim,g)) ans=mid,r=mid-1;else l=mid+1; }if (l>n) {puts("-1");continue;}// printf("%d\n",ans); printf("%d\n",jui[ans].d); }}int main(){// freopen("juice.in","r",stdin);// freopen("juice.out","w",stdout); n=read();m=read(); for (int i=1;i<=n;++i){ jui[i].d=read();jui[i].p=read();jui[i].l=read(); }gao(); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。