GESP 202506 5级真题「奖品兑换」题解
这篇题解讲的是 GESP 2025 年 6 月五级的一道题目“奖品兑换”。题目要求用两种面值的兑换券兑换奖品，求能兑换的最大数量，数据规模高达 10^9，直接暴力枚举肯定超时，而想设计一个万无一失的贪心策略又很困难。 作者的核心解法是“二分答案+判定”。关键思路在于：兑换券数量越多，所需的另一种券就越多，满足单调性，因此可以对最大兑换数进行二分搜索。对于每一个待检验的答案 k，先按“全都用大面值券兑换”的方式计算，如果小面值券超额了，就逐步将部分兑换方案切换为使用小面值券，通过计算需要切换的次数（涉及向上取整）来判断是否在总券数内可行。 整道题综合考查了二分搜索、数学推导（包括向上取整的代码写法）以及对数据范围的敏感度。题目设计有区分度：没想到二分的同学用贪心或暴力也能拿到部分分数，而想出最优解则能全面锻炼算法思维。代码实现时还需要注意用 `long long` 防止溢出。