A61987 奖品兑换

由于我考五级时想看题解都要切洛谷，非常麻烦，为了造福后人，所以发具体题解

---

题意:
可以使用 a张课堂优秀券 和 b张作业优秀券 兑换一份奖品，这是方式1
可以使用 b张课堂优秀券 和 a张作业优秀券 兑换一份奖品，这是方式2
现在有 n张课堂优秀券 和 m张作业优秀券 问 最多 能兑换多少份奖品

---

讲解:
现在我们有两种方式获得奖品，那么我们可以
设 最多 共可换 k 份奖品，且用 方式1 可换 x 份奖品
则用 方式2 可换 k-x 份奖品

那么
课堂优秀券=ax + b(k - x),整理可得 课堂优秀券=(a - b)x + bk
作业优秀券=bx + a(k - x),整理可得 作业优秀券=(b - a)x + ak
但是 使用的课堂优秀券总数 一定 不会超过 原来的课堂优秀券总数
同理 使用的作业优秀券总数 一定 不会超过 原来的作业优秀券总数

可得
(a - b)x + bk≤n
(b - a)x + ak≤m

这时发现，若a=b,则含x的项为0，b也可以替换为a
则 当a=b时,k ≤ n/b , k ≤ m/a
取其 交集 则 k=min(n/b , m/a) , 由于b可替换为a , 原式为k=min(n/a , m/a)

若a≠b, 分两种情况 ①,a>b ②,a<b
原式为
(a - b)x + bk≤n，①式
(b - a)x + ak≤m，②式
由 ①式 得 (a-b)x ≤ n-bk, 则 x ≤ (n - bk) / (a - b)
同理
由 ②式 得 (b-a)x ≤ m-ak, 两边同乘-1 , 则 (a - b)x ≥ ak - m, 得 x ≥ (ak - m) / (a - b)

情况①，a>b时
x ≤ (n - bk) / (a - b)且x ≥(ak - m) / (a - b)
情况②，a<b时
x ≥ (n - bk) / (a - b)且x ≤(ak - m) / (a - b)

其实这就是二分答案的上界和下界, 那么整体就是一个二分的思路了
但是问题又来了，如何定初始的范围呢？
首先，要明白，我们去查找的答案应该是k,再判断由k得出的x的上界是否大于等于 下界
那么k一定不会是负数，所以左区间为0（最小）
右区间则取max(n,m)/min(a,b),以保证尽量大且包含答案（不一定要这个，只要够大但别太大即可）

但又会发现，在编写check检查时，会出现精度问题，所以上下界应该用double存储
可是用double会出现小数，上下界是不能为小数的，四舍五入又会多出一位，答案出现偏差
所以下界我们要向上取整，上界要向下取整
由于下界可能小于0，所以下界取max(下界，0)（这里的0要与下界为同一类型）
上界可能大于k,所以上界取min(上界，k)(这里的k要与上界为同一类型)
最后判断上界是否大于等于下界即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//以防万一，整型全用long long
ll n,m,a,b;
bool check(ll k){
    double up,low;//上下界
    if(a>b){//情况①
        up=(n-b*k*1.0)/(a-b);//整数变小数乘1.0,下同
        low=(a*k*1.0-m)/(a-b);
    }else{//情况②
        low=(n-b*k*1.0)/(a-b);
        up=(a*k*1.0-m)/(a-b);
    }
    ll l=ceil(low);
    ll r=floor(up);
    l=max(l,(ll)0);//类型统一
    r=min(r,k);
    return(l<=r);
}
int main(){
    cin>>n>>m;
    cin>>a>>b;
    if(a==b){//特判
        cout<<min(n/a,m/a);
        return 0;
    }
    ll l=0,ans=0;//左区间 和 答案存储
    ll r=max(n,m)/min(a,b);//右区间
    while(l<=r){
        ll mid=(l+r)/2;//二分
        if(check(mid)){
            ans=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    cout<<ans;
    return 0;
}

由于此题Acgo测试点太水了所以提交到洛谷

正常通过
题目链接：https://www.luogu.com.cn/problem/P13013
对应的选择判断：https://ti.luogu.com.cn/problemset/1185

制作不易，有错指出，有用留下一句谢谢就行了