GESP C++ 真题深度分析:二分答案(26年3月五级第七题)

四季读书网 2026-04-17 11:27:02 1 0

GESP C++ 真题深度分析：二分答案（26年3月五级第七题）

题目要求阅读代码，计算下⾯程序的运⾏结果为什么？

bool check(int n, int a[], int k, int dist){
    int cnt = 1;
    int last = a[0];
    for (int i = 1; i < n; i++) {
        if (a[i] - last >= dist) {
            cnt++;
            last = a[i];
        }
    }
    return cnt >= k;
}
int solve(int n, int a[], int k){
    std::sort(a, a + n);
    int l = 0;
    int r = a[n - 1] - a[0];
    while (l < r) {
        int mid = (l + r + 1) / 2;
        if (check(n, a, k, mid)) 
            l = mid;
        else
            r = mid - 1;
    }
    return l;
}
int main(){
    int a[] = {1, 2, 8, 4, 9};
    int n = 5;
    int k = 3;
    std::cout << solve(n, a, k) << std::endl;
    return 0;
}

这段代码实现了一个经典的算法问题：最小值最大化（Maximize the Minimum Distance）。

具体来说，它解决的问题通常被称为 “牛栏问题” 或 “跳石头问题” 的变种。

• 牛栏问题：在一条直线上，有 n个牛栏（位置固定），要将 k头牛放入其中，使得任意两头牛之间的最小距离尽可能大。
• 跳石头问题：一条长度为 L的河道，起点在位置 0，终点在位置 L。中间有 N块岩石（不含起点和终点），位置已知且按升序给出。选手从起点出发，依次跳到终点。最多可以移走 M块岩石（起点和终点不可移动）。

如果不仔细阅读代码，我们就可以根据升序排列{1,2,4,8,9}，推断出来1,4,8 是最优解，因此答案就是 3。

一、如何阅读代码，掌握其主要功能

前面我学习过，要快速判断一个二分答案问题是“最大值最小化”还是“最小值最大化”，可以从代码的两个核心部分入手：二分查找的主体逻辑和判定函数（check函数）的写法。

1. 观察二分主体逻辑

这是最直接、最可靠的判断依据。二分主体的写法直接决定了我们是在寻找满足条件的“最大值”还是“最小值”。

• 最大值最小化问题，本质是找“最小值”，即最小的最大值

• 首先，L 和 R是两个边界，定义了一个要进行二分的区间，该区间是升序的。
• 特征：当 check(mid) 为真时，说明当前值 mid 可行，但我们要找的是最小的可行值，因此需要向左侧（更小的值）继续搜索。

• 代码模式：

if (check(mid)) {
    R = mid - 1; // 可行，尝试寻找更小的值
} else {
    L = mid + 1;  // 不可行，必须增大值
}

• 最小值最大化问题，本质是找“最大值”，即最大的最小值

• 特征：当 check(mid) 为真时，说明当前值 mid 可行，但我们要找的是最大的可行值，因此需要向右侧（更大的值）继续搜索。

• 代码模式：

if (check(mid)) {
    L = mid + 1;  // 可行，往右侧找，尝试寻找更大的值
} else {
    R = mid - 1; // 不可行，往左侧找，必须减小值
}

简单来说，check(mid) 为真时，往小的区间移动，还是往大的区间移动，是区分这两类问题的关键。

2. 分析判定函数（check函数）

判定函数揭示了问题的单调性，即答案的可行性如何随数值变化。

• 最大值最小化问题，判定第一个满足条件的最大值

• 逻辑：我们寻找一个上限。如果一个较大的值 X 能满足条件（例如，所有分组和都 <= X），那么任何比 X 更大的值也一定能满足。
• 可行性趋势：随着 mid 值的增大，可行性从 不可行 (False) 变为可行 (True)。

• mid 太小 → 条件苛刻 → 难以满足 → check(mid) 返回 false
• mid 足够大 → 条件宽松 → 容易满足 → check(mid) 返回 true

• 目标：找到这个从 false 变为 true 的分界点，即第一个可行的值。

• 最小值最大化问题，判定最后一个满足条件的最小值

• 逻辑：我们寻找一个下限。如果一个较大的值 X 能满足条件（例如，所有间距都 >= X），那么任何比 X 更小的值也一定能满足。
• 可行性趋势：随着 mid 值的增大，可行性从 可行 (True) 变为不可行 (False)。

• mid 较小 → 条件宽松 → 容易满足 → check(mid) 返回 true
• mid 太大 → 条件苛刻 → 难以满足 → check(mid) 返回 false

• 目标：找到这个从 true 变为 false 的分界点，即最后一个可行的值。

3. 总结

• 移动的方向管最大化最小化

1. 最小化：check 为 true后，继续往小的区间（左边）去尝试计算更小的情况；
2. 最大化：check 为 true后，继续往大的区间（右边）去尝试计算更大的情况；

• check函数的逻辑管最大值最小值

• 最大值：mid 越大越可行，越宽松，R就是上限；
• 最小值：mid 越小越可行，越宽松，L就是下限；

根据理解，自行分析数据，理论上可以观察出正确的结果，不需要进行计算即可。（注：这个是我当前学习深度的理解，不一定100%准确，后面多做题再领悟）。

二、代码功能分析，推演运算过程

1. 核心逻辑拆解

代码主要由三部分组成：check 函数、solve 函数和 main 函数。

• check 函数（贪心验证）：

• 作用： 验证是否能在数组中选出至少 k 个点，使得它们之间的间距至少为 dist。
• 逻辑：

1. 首先选择第一个点 a（贪心策略：为了留出更多空间给后面的点，第一个点越早选越好）。
2. 遍历后续的点，如果当前点 a[i] 与上一个选中的点 last 的距离大于等于 dist，则选中该点，并更新 last。
3. 最后判断选中的点的数量 cnt 是否大于等于 k。

• 返回值：true 表示可行（距离 dist 可以满足），false 表示不可行。

• solve 函数（二分答案）：

• 预处理：std::sort(a, a + n); 首先对位置数组进行排序，因为贪心策略依赖于有序的位置。
• 二分查找：

• 搜索范围：l = 0 到 r = a[n-1] - a（最小距离的可能范围是从0到最大跨度）。
• 核心技巧：int mid = (l + r + 1) / 2; 这里使用了向上取整。这是二分查找求右边界（最大化答案）的标准写法。

• 如果 check(mid) 为真，说明距离 mid 是可行的，我们尝试更大的距离，所以 l = mid。
• 如果 check(mid) 为假，说明距离 mid 太大了，需要减小，所以 r = mid - 1。
• 注意： 如果使用 (l+r)/2 且 l = mid，当 l 和 r 相邻时（例如 l=3, r=4），mid 会一直是 3，导致死循环。因此必须加 1。

• main 函数（执行）：

• 输入数组 {1, 2, 8, 4, 9}，需要选 k=3 个点。
• 排序后数组为 {1, 2, 4, 8, 9}。
• 调用 solve 并输出结果。
•

这个有个细节要注意：对应 (l+r)/2 的安全写法的不同形式
mid = l + (r - l) / 2 : 向下取整、防溢出、左偏中点。
mid = (l + r + 1) / 2：向上取整、右偏中点。防溢出的安全等价写法是 l + (r - l + 1) / 2。

2. 执行过程推演

手动模拟一下 main 函数的执行：

1. 排序： 数组变为 `{1,2,4,8,9}`。
2. 二分范围：l = 0, r = 9 - 1 = 8。
3. 循环过程：

• 第1轮：l=0, r=8。mid = (0+8+1)/2 = 4。

• 调用 check(dist=4)：

• 选 1。
• 2-1 < 4 (跳过)。
• 4-1 < 4 (跳过)。
• 8-1 >= 4 (选 8, cnt=2)。
• 9-8 < 4 (跳过)。
• 最终 cnt=2，小于 k=3。返回 false。

• 结果：r = 4 - 1 = 3。

• 第2轮：l=0, r=3。mid = (0+3+1)/2 = 2。

• 调用 check(dist=2)：

• 选 1。
• 2-1 < 2 (跳过)。
• 4-1 >= 2 (选 4, cnt=2)。
• 8-4 >= 2 (选 8, cnt=3)。
• cnt >= 3，返回 true。

• 结果：l = 2。

• 第3轮：l=2, r=3。mid = (2+3+1)/2 = 3。

• 调用 check(dist=3)：

• 选 1。
• 4-1 >= 3 (选 4, cnt=2)。
• 8-4 >= 3 (选 8, cnt=3)。
• cnt >= 3，返回 true。

• 结果：l = 3。

• 第4轮：l=3, r=3。循环结束。

4. 输出：3。

通过认真的推演，可以得出3这个结果，跟猜测的结果一致，基本上是 100% 拿分了。同样的，可以记住这个模版，我估计是个常考的题目，等做后面真题再验证吧。

三、详细的代码注释

AI工具时刻到了，下面是让千问给添加的注释，辅助我验证自己的理解。还有一种做法是咱们自己写注释，让AI工具挑毛病，这个的学习效果会更好一些。

#include <iostream>
#include <algorithm>
#include <vector>

/**
 * 验证函数：检查在最小距离为 dist 的情况下，能否放下至少 k 个点（牛）
 * 使用贪心策略：总是尽可能早地放置下一个点，以便给后面留出更多空间
 */
bool check(int n, int a[], int k, int dist){
    int cnt = 1;          // 计数器：记录当前已经放置了多少个点
    int last = a[0];      // 记录上一个放置点的位置。贪心策略：第一个点一定放在最左边 a[0]

    // 遍历剩下的位置
    for (int i = 1; i < n; i++) {
        // 如果当前位置 a[i] 与上一个放置点 last 的距离 >= 要求的距离 dist
        if (a[i] - last >= dist) {
            cnt++;        // 成功放置一个点
            last = a[i];  // 更新上一个放置点的位置
        }
    }
    // 如果实际放置的点数 >= 需要的点数 k，说明距离 dist 是可行的
    return cnt >= k;
}

/**
 * 主求解函数：使用二分答案法寻找最大的最小距离
 */
int solve(int n, int a[], int k){
    // 1. 预处理：二分答案通常要求数组有序（贪心策略依赖顺序）
    std::sort(a, a + n);

    // 2. 确定二分边界
    int l = 0;                  // 左边界：最小距离至少为 0
    int r = a[n - 1] - a[0];    // 右边界：最大距离不会超过首尾之差

    // 3. 二分查找
    while (l < r) {
        // 【关键点】：这里使用 (l + r + 1) / 2 进行向上取整
        // 原因：后续逻辑是 l = mid。如果不加 1，当 l 和 r 相邻时（如 l=3, r=4），
        // mid 会一直是 3，导致 l=3 死循环。
        int mid = (l + r + 1) / 2;

        // 检查距离 mid 是否可行
        if (check(n, a, k, mid)) {
            // 如果可行，说明 mid 是一个可能的答案，但也许还能更大
            // 所以收缩左边界，保留 mid
            l = mid;
        } else {
            // 如果不可行，说明距离 mid 太大了，必须减小
            // 所以收缩右边界，排除 mid
            r = mid - 1;
        }
    }

    // 循环结束时 l == r，即为所求的最大最小距离
    return l;
}

int main(){
    // 测试数据：牛栏的位置
    int a[] = {1, 2, 8, 4, 9};
    int n = 5;  // 牛栏数量
    int k = 3;  // 需要放置的牛的数量

    // 调用函数并输出结果
    // 预期逻辑：排序后为 1, 2, 4, 8, 9。选 1, 4, 8 或 1, 4, 9 等，最大最小距离为 3
    std::cout << solve(n, a, k) << std::endl;

    return 0;
}