CF 1538 G. Gift Set (贪心+思维)

链接

题意：

Polycarp有x个红糖和y个蓝糖，现在他想用这些糖果做一些礼品盒（gift set），但规定每个礼品盒里必须有a个红糖、b个蓝糖或b个红糖、a个蓝糖。现在求他最多能做成多少个礼品盒。

分析：

首先我们会发现这个题有很多种方法：二分()，模拟(),模拟退火等，

二分：

既然他是最多能做多少，那么我们可以发现，答案满足单调性，那么我们直接二分答案就好了。
首先我们找到那个用的糖果更少，假设a的更少。那么我们枚举的答案，一定满足：这是肯定的，因为如果用的少的都不满足跟不用提多的了，然后我们看如果那么他一定是满足条件的，否则就是我们就要看这样就是满足条件的，否则不满足。为什么那？其实就是用剩下的空变化一下成b,由a变成b需要加上所以我们看有多少可以转化成b，如果比ans大或者相等那么这个ans是可以的，否则就不可以。

void solve(){
scanf("%lld%lld%lld%lld", &n, &m, &a, &b);
if(a>b) swap(a,b);
ll l=0,r=1e9+7;
while(l<r){
ll mid=(l+r)/2;
ll x=n,y=m;
x-=a*mid;
y-=a*mid;
bool flag=(x>=0&&y>=0);
if(b>a){///防止出现a=b导致除以负数
if(x/(b-a)+y/(b-a)<mid) flag=0;
}
if(flag) l=mid+1;
else r=mid;
}
cout<<l-1<<endl;
}

模拟()

我们让n<m,a<b
我们分析出来他其实就是那么 一些(a+b,a+b)这样的二元组，和一些(a,b)这样的二元组。
我们发现我们选一个二元组(a,b)会让(n,m)之间的差缩减(b-a).所以我们可以先选个(a,b)剩下的可以全选(a+b,a+b);

如果我们最后选完(a+b,a+b)，还剩的够再买一个(a,b)或者(b,a)这样的二元组，那么我们就需要在做一次贡献。

需要特判一下,a=b因为不能除以0.答案是()

void solve()
{
scanf("%lld%lld%lld%lld", &n, &m, &a, &b);
///O（1）
if(n>m) swap(n,m);
if(a>b) swap(a,b);
if(n<a||m<b) {
puts("0");
return ;
}
ll ca=m-n,cb=b-a;
if(cb==0){
printf("%lld\n",n/a);
return;
}
ll num=min(ca/cb,min(n/a,m/b));
n-=num*a;m-=num*b;
ll ans=num+min(n,m)/(a+b)*2;
if(n>=a&&m>=b) n-=a,m-=b,num++;
printf("%lld\n",max(ans,num+min(n,m)/(a+b)*2));
}