题解：P13013 [GESP202506 五级] 奖品兑换

· · 题解

Solution

一道贪心和二分题，本人没场切，只拿了暴力分，回来补篇题解。

我们可以把这个过程看成先进行很多次第一种兑换，再将其中的一部分第一种兑换替换为第二种兑换先进行 k 次第一种兑换，那么课堂优秀券还剩 n-ak，作业优秀券还剩 m-bk 。

将一次第一种兑换更改为第二种，也就是原来的 -a,-b 变成了 -b,-a，可以看作是将 b-a 张课堂优秀券转化成了 b-a 张作业优秀券。

所以我们可以进行很多次第一种兑换，即使把作业优秀券兑换成了负数也没关系，可以用剩下的课堂优秀券进行转化。

即：

n - ak ≥0 n - ak ≥ bk - m k=\min(\lfloor \frac{n}{k} \rfloor,\lfloor \frac{n+m}{a+b} \rfloor)

之后可以将 n,m 互换，整个过程用二分进行优化。

当然有听说有 O(1) 做法的更好可以参考。

AC code

#include <bits/stdc++.h>
using namespace std;
long long n,m,a,b,l,r;
int check(int v) 
{
    long long x,y,t;
    x=v*a;
    y=v*b;
    if(y>m)
    {
        t=(y-m+(b-a)-1)/(b-a);
        y-=t*(b-a);
        x+=t*(b-a);
    }
    return x<=n&&y<=m;
}
int main() 
{
    cin>>n>>m>>a>>b;
    if(a>b) swap(a,b);
    if(n>m) swap(n,m);
    if(a==b)
    {
        cout<<n/a;
        return 0;
    }
    l=0,r=n;
    while(l<r) 
    {
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<r;
    return 0;
}