二分答案

方法：二分答案

设总共兑换 k 份奖品，其中：

• x 份用方案1
• y 份用方案2（y = k - x）

约束条件：

1. 课堂券：ax + by ≤ n
2. 作业券：bx + ay ≤ m

将 y = k - x 代入：

• ax + b(k-x) ≤ n → (a-b)x ≤ n - bk
• bx + a(k-x) ≤ m → (b-a)x ≤ m - ak

我们需要判断是否存在合法的 x 使得两个约束都满足。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, m, a, b;

// 检查能否兑换 k 份奖品
bool check(ll k) {
    // 约束：
    // ax + b(k-x) <= n  →  (a-b)x <= n - bk
    // bx + a(k-x) <= m  →  (b-a)x <= m - ak
    
    if (a == b) {
        // 两种方案等价
        return (a * k <= n && a * k <= m);
    }
        ll L = 0, R = k;  // x 的范围是 [0, k]
    
    // 约束1: (a-b)x <= n - bk
    ll c1 = n - b * k;
    ll d1 = a - b;
    if (d1 > 0) {
        if (c1 < 0) return false;  // 无解
        R = min(R, c1 / d1);
    } else if (d1 < 0) {
        if (c1 >= 0) {
            // x >= 负数，x>=0 已满足
        } else {
            // c1 < 0, d1 < 0: 需要向上取整
            ll t = c1 / d1;
            if (c1 % d1 != 0) t++;
            L = max(L, t);
        }
    }
    
    // 约束2: (b-a)x <= m - ak
    ll c2 = m - a * k;
    ll d2 = b - a;
    if (d2 > 0) {
        if (c2 < 0) return false;
        R = min(R, c2 / d2);
    } else if (d2 < 0) {
        if (c2 >= 0) {
            // 无额外约束
        } else {
            ll t = c2 / d2;
            if (c2 % d2 != 0) t++;
            L = max(L, t);
        }
    }
    
    return L <= R;
}

int main() {

    
    cin >> n >> m;
    cin >> a >> b;
    
    // 二分答案
    ll l = 0, r = (n + m) / min(a, b) + 1, ans = 0;
    while (l <= r) {
        ll mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
    
    cout << ans << endl;
    return 0;
}