唐巧的博客

GESP 202506 5级真题「奖品兑换」题解

cspj
字数统计: 769阅读时长: 3 min
2025/07/01

题目描述

分析

此题首先是不能暴力枚举的，因为 n 和 m 最大情况下是 10^9，这个数据规模，暴力枚举肯定会超时。

然后我们可能想到贪心，但实际可落地的贪心的策略总是有特殊情况。

最后，假如我们可以检查一个答案是否可行，我们就可以用二分答案+判定的方法求解。

二分还有一个要求，就是答案是单调递增的。我们可以想像，随着兑换券的递增，如果限定 n 的值不变，那 m 的值肯定是递增的。所以此题符合单调递增的条件。

解法

那么，对于一个可能的答案 k，我们怎么检查答案是否可行呢？

  • 我们先把 n 和 m 排序，让 n 是较大者，a 和 b 排序，让 a 是较大者
  • 对于一份奖品，可以是 n-a, m-b 来获得，也可以是 n-b, m-a 来获得，我们让 d=a-b
  • 因为 a 是较大者，所以当更换兑换方式的时候，n 的值从n-a变成了n-b，相对来说，增加了 d，m 的值减少了 d

所以：

  • 我们可以先用第一个兑换方法，把 k 个奖品换成 c1=a*k 张课堂优秀券, c2=b*k 张作业优秀券
  • 如果 c1 <=n, c2 <= m 那这个答案 k 显然就是可以的。
  • 但如果 c1 > n，我们可以想到，把超额出来的兑换换成第二个兑换方法

具体如何换呢？

  • 我们先计算超额的值，为 c1-n
  • 每次兑换可以让这个值少 d，所以需要换 r=(c1-n)/d (向上取整) 即 r=(c1-n+d-1)/d个
  • 经过如上的兑换，c1 的值减少了 d*r，c2 的值增加了 d*r

最后需要注意，因为 a*k 的范围可能超过 int，所以需要把计算过程都用 long long 来保存。

总结

此题考查了：

  • 二分+判定的解法
  • 向上取整的写法
  • 数据范围的预估
  • 时间复杂度的预估

这还是非常综合的一道题。对于没想到二分的学生，也可以用贪心或者暴力枚举骗到不少分（估计 10-15 分），所以此题也有相当的区分度，各种能力的学生都可以拿到部分分数。

详细代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*
 * Author: Tang Qiao
 */
#include <bits/stdc++.h>
using namespace std;

long long n, m, a, b, d, ans;

bool test(long long k) {
    long long c1 = a*k;
    long long c2 = b*k;
    if (c1 > n) {
        long long r = (c1 - n + d - 1) / d;
        c1 -= r*d;
        c2 += r*d;
    }
    if (c1 <= n && c2 <=m) return true;
    else return false;
}

int main() {
    ios::sync_with_stdio(0);       
    cin >> n >> m >> a >> b;
    if (n < m) swap(n, m);
    if (a < b) swap(a, b);
    d = a - b;
    long long l = 0;
    long long r = n;
    while (l <= r) {
        long long m = (l+r)/2;
        if (test(m)) {
            ans = max(ans, m);
            l = m+1;
        } else {
            r = m-1;
        }
    }
    cout << ans << endl;
    return 0;
}

原文作者：唐巧

原文链接：https://blog.devtang.com/2025/07/01/gesp-level5-202506-1/

发表日期：七月 1日 2025, 10:29:46 晚上

更新日期：July 1st 2025, 11:02:04 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 题目描述
  2. 2. 分析
  3. 3. 解法
  4. 4. 总结
  5. 5. 详细代码
Total : 355
2025
2024
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
anniversary Git startup writing Interview books Swift blog 投稿 PM cooking supply-chain marketing cspj summary
iOS shell mac summary iOS weekly