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

Clouds_dream · 2025-06-30 21:41:04 · 题解

前言

一道很好的二分练手题。

题目内容

题目传送门

题目分析

我们假设用第一种方式兑换了 x 次，用第二种方式兑换了 y 次，则总次数 k = x + y，并且满足 a \cdot x + b \cdot y \le n 和 b \cdot x + a \cdot y \le m，且 x 与 y 都为非负整数。

因为每次兑换至少消耗 a 张课堂优秀券和 a 张作业优秀券（当 a \le b 时），所以 ans 的上界为 \min(\lfloor n / a \rfloor, \lfloor m / a \rfloor)。

对于给定的 k，检查是否有 x（第一种方式兑换了 x 次，则第二种方式兑换了 k - x 次）满足：

• a \cdot x + b \cdot (k - x) \le n
• b \cdot x + a \cdot (k - x) \le m

整理得：

• (b-a) \cdot x \ge b \cdot k - n $ $(b > a)
• (b-a) \cdot x \le m - a \cdot k $ $(b > a)

计算 x 的可行区间，如果非空则 x 可行。

边界处理：

• 当 a = b 时，直接记录答案。
• 当 a < b 时，先计算总券数是否够，然后计算 x 的区间。

上代码（知道你们直接看这个）

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'

#define int long long

#define fst ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define prq priority_queue

#define uns unordered_set

#define freopen freopen(".in","r",stdin);freopen(".out","w",stdout);

const int P = 998244353;

const int INF = 0x3f3f3f3f3f3f3f3f;

const int N = 1e6+10, M = 1e8 + 10;

int __lcm(int a,int b){return a/__gcd(a,b)*b;}

int n,m,a,b;
int ans=0;

signed main()
{
    fst
    cin>>n>>m>>a>>b;
    if(a>b)swap(a,b);//确保a<=b
    int l=0,r=min(n/a,m/a);//左右区间
    while(l<=r){
        int mid=(l+r)/2;
        if(a==b){
            ans=mid;
            l=mid+1;
        }//情况1
        else{
            if((a+b)*mid>n+m){
                r=mid-1;
                continue;
            }
            int mi=0;
            if(b*mid>n){
                mi=(b*mid-n+b-a-1)/(b-a);//左端点
            }
            int ma=(m-a*mid)/(b-a);
            ma=min(ma,mid);//右端点
            if(ma>=0&&mi<=ma){
                ans=mid;
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }//情况2
    }
    cout<<ans;
    return 0;
}

UPD

2025.7.2 感谢 @pika_ 大佬指出的错误。