y

GESP C++ 5级的题目，已经不能直观看出来或者用模拟枚举解决了。 那么读到题目，该怎么分析， 以真题为例GESP C++ 5级 P13013 奖品兑换

1. 很多题目直接求答案很难，但“验证一个答案”很简单

算法思想一句话：

不会直接求最优解？

那就二分猜答案，把问题变成判断题。

2. 资源限制天然就是「不等式」

限制 = 不等式

 多个不等式 = 求交集

这直接引导走向：

• •

  设未知数

• •

  列不等式

• •

  化简

• •

  判断是否有解

（这是 GESP 五级二分答案 + 不等式的核心部分）

一）、原始建模（一定要先清楚这个）

设：

• 用第一种方案（花 a课 + b作）共 x₁ 次

• 用第二种方案（花 b课 + a作）共 x₂ 次

显然：

x1+x2=x

券的限制是：

{ax1+bx2≤n(课堂券)bx1+ax2≤m(作业券)

二）、消去 x₂

因为 x2=x−x1，代入两个不等式：

课堂券：

ax1+b(x−x1)≤n⇒(a−b)x1≤n−bx

作业券：

bx1+a(x−x1)≤m⇒(b−a)x1≤m−ax

注意：

b−a=−(a−b)

所以第二个不等式变为：

−(a−b)x1≤m−ax⇒(a−b)x1≥ax−m

三）、关键一步：让 a ≥ b

因为题目完全对称：

• (a,b)和 (b,a)没有本质区别

• 所以可以 强制规定：

a≥b⇒a−b>0

这样 除以 (a−b) 时不等号方向不变，非常安全！

四）、整理成 x₁ 的范围

现在两个不等式是：

两边同时除以 a−b>0：

五）、加上 x₁ 的自然限制

x₁ 是“第一种方案用了多少次”，必须满足：

0≤x1≤x

所以要取交集：

六）、这个式子在干什么？

只要这个区间里还有整数，x 就是可行的

七）、举例（样例 1）

n=8, m=8
a=2, b=1

取 x = 5：

• a−b=1

• 左端：12×5−8=2

• 右端：18−1×5=3

2≤x1≤3

存在整数 → x = 5可行 

八）、为什么这样就能二分？

• 如果某个 x可行 → 更大的 x也可能可行

• 如果不可行 → 再大一定更不行

符合：单调性成立，二分合法

九、一句话总结

设兑换总数为 x，

利用对称性令 a ≥ b，

用 x₁表示第一种方案次数，

推出 x₁的整数存在区间，

判断区间是否非空即可二分答案。

4. 怎么发现这种突破口？（通用）

遇到类似题，按这个顺序问

 第 1 问：

“答案越大越难吗？”

→ 是 →  可以二分

 第 2 问：

“验证一个答案，是不是比直接算简单？”

→ 是 →  二分 + 判定

第 3 问：

“有没有资源限制？”

→ 有 →  列不等式

 第 4 问：

“有没有对称性？”

→ 有 →  不妨设大小

 第 5 问：

“变量太多？”

→ 是 →  消元，留一个自由变量

C++代码

#include<bits/stdc++.h>using namespace std;typedef long long LL;intmain(){    LL n, m, a, b;    cin >> n >> m >> a >> b;    if (a < b) swap(a, b); // 确保 a >= b    if (a == b) { // 特判        cout << min(n / a, m / a) << endl;        return 0;    }    LL diff= a - b;    LL left = 0, right = (n + m) / (a + b), ans = 0;    while (left <= right) {        LL mid = (left + right) / 2;        // 计算 Lx = ceil((a*mid - m)/diff)        LL num_L = a * mid - m;        LL Lx = (num_L <= 0) ? 0 : (num_L + diff - 1) / diff;        // 计算 Rx = floor((n - b*mid)/diff)        LL num_R = n - b * mid;        if (num_R < 0) {            right = mid - 1;            continue;        }        LL Rx = num_R / diff;        if (Rx > mid) Rx = mid;        if (Lx <= Rx) {            ans = mid;            left = mid + 1;        } else {            right = mid - 1;        }    }    cout << ans << endl;    return 0;}