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

非常不错的一道二分答案题目，整体不算太难。

思路如下：我们需要确定最多能兑换多少份奖品。兑换一份奖品可以使用两种方式：一种是使用

a

张课堂优秀券和

b

张作业优秀券，另一种是使用

b

张课堂优秀券和

a

张作业优秀券。

给出

n

张课堂优秀券和

m

张作业优秀券，我们需要找出最大的兑换份数

mid

，使得存在非负整数

x

和

y

，其中

x+y=mid

，需要满足以下条件：

$a\times x + b \times y \le n$
$b\times x + a \times y \le m$

使用二分法来寻找最大的

mid

。二分范围的下界为

0

，上界为

\max(n,m) / \min(a,b) + 1

（确保覆盖可能的解）。同时，检查函数中对于每个候选的

t

，检查是否存在非负整数

x（0 \le x \le t）

满足：

$(a - b)\times x \le n - b\times t$
$(a - b) \times x \ge a \times t - m$

根据

a

和

b

的大小关系，分情况处理：

当 $a$ 和 $b$ 相等时，只需验证 $a\times t \le n$ 且 $a\times t ≤ m$ 。
当 $a > b$ 时，计算 $x$ 的下界和上界，并检查是否存在整数 $x$ 在 $[0, t]$ 范围内。
当 $a < b$ 时，同样计算 $x$ 的下界和上界，并检查是否存在整数 $x$ 在 $[0, t]$ 范围内。

剩下就是二分答案的模板了，相信大家都可以看懂，上代码：

CPP

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

long long n, m, a, b;

bool check(long long t){

    if((a + b) * t > n + m) 
        return false;

    if(a == b){
        if( a * t <= n &&  a * t <= m)
            return true;
        else
            return false;
    }

    double low, high;
    if(a > b){
        low = (1.0 * a * t - m) / (a - b);
        high = (1.0 * n - b * t) / (a - b);
    }
    else{
        low = (1.0 * n - b * t) /(a - b);
        high = (1.0 * a * t - m) /(a - b);
    }

    long long L = ceil(low);
    long long R = floor(high);

    L = max(L, (long long)0);
    R = min(R, t);

    return(L <= R);
}

int main(){

    cin >> n >> m;
    cin >> a >> b;

    long long ans = 0;
    long long left = 0;
    long long right = max(n,m)/min(a,b) + 1;
    
    while(left <= right){
        long long mid =(left + right) / 2;
        if(check(mid)){
            ans = mid;
            left = mid + 1;
        }
        else{
            right = mid - 1;
        }
    }

    cout << ans;

    return 0;
}

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

文章操作

相关推荐

评论

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