CF1538G.Gift Set（二分）

传送门

题意：

有(x)个红糖果和(y)个蓝糖果，有两种礼物包装方式：
(1.a)个红糖果(+b)个蓝糖果
(2.b)个红糖果(+a)个蓝糖果
求最多能够打包成多少个礼物

思路：

假设第一种打包了(c)个礼物，第二种打包了(d)个礼物，一共打包了(c+d)个礼物。
考虑二分答案，也就是(c+d=mid)
又因为
(a*c+b*d<=x)
(a*d+b*c<=y)
所以
(c<=(x-b*mid)/(a-b))
(d<=(y-b*mid)/(a-b))
注意特判分母为(0)的情况

代码：

ll x,y,a,b;

int check(ll mid){
	ll c=x-b*mid,d=y-b*mid;
	if(a==b){
		if(c>=0&&d>=0) return 1;
		return 0;
	}
	else{
		if(c<0||d<0) return 0;
		c/=(a-b),d/=(a-b);
		if(c+d>=mid) return 1;
		return 0;
	}
}

int main(){
	int _=read;
	while(_--){
		x=read,y=read,a=read,b=read;
		if(a<b) swap(a,b);
		//if(x<y) swap(x,y);
		ll l=0,r=1e9,res;
		while(l<=r){
			ll mid=(l+r)/2;
			if(check(mid)) res=mid,l=mid+1;
			else r=mid-1;
		}
		cout<<res<<endl;
	}
	return 0;
}