G5015 [GESP202506 五级] 奖品兑换 题解

知识点：二分答案、不等式、整数边界。

解题思路

二分可兑换总数k。设其中一种方向选x次，把两种材料消耗的不等式整理成x的整数上下界，区间非空即能完成k次。

为什么正确

每个合法兑换组合唯一对应x，两个资源约束恰给出可行区间；可兑换数越小越容易满足，因此可二分最大k。

易错点

a==b时单独判断；上取整与负数整除要按代码推导，不能直接使用浮点近似。

复杂度

时间O(log(n+m))，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n,m,a,b;
    cin>>n>>m>>a>>b;
    if(a>b)swap(a,b);
    auto ok=[&](long long k) {
        if(a==b)return k*a<=min(n,m);
        long long delta=b-a;
        long long lo=max(0LL,(k*b-m+delta-1)/delta);
        long long hi=min(k,(n-k*a)/delta);
        if(n<k*a)return false;
        return lo<=hi;
    }
    ;
    long long lo=0,hi=(n+m)/(a+b);
    while(lo<hi) {
        long long mid=(lo+hi+1)/2;
        if(ok(mid))lo=mid;
        else hi=mid-1;
    }
    cout<<lo;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。