CSP-S 提高级 · CSP 2025 提高级第一轮 第 17 题

#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
int cnt_broken = 0;
int cnt_check = 0;
int n, k;
inline bool check(int h) {
    printf("now check:%d\n", h);
    ++cnt_check;
    if (cnt_broken == 2) {
        printf("You have no egg!\n");
        return false;
    }
    if (h >= k) {
        ++cnt_broken;
        return true;
    } else {
        return false;
    }
}
inline bool assert_ans(int h) {
    if (h == k) {
        printf("You are Right using %d checks\n", cnt_check);
        return true;
    } else {
        printf("Wrong answer!\n");
        return false;
    }
}
inline void guess1(int n) {
    for (int i = 1; i <= n; ++i) {
        if (check(i)) {
            assert_ans(i);
            return;
        }
    }
}
inline void guess2(int n) {
    int w = 0;
    for (w = 1; w * (w + 1) / 2 < n; ++w)
        ;
    for (int ti = w, nh = w;; --t

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题本质是扔鸡蛋问题的变种，核心在于理解 guess1 的线性扫描与 guess2 的等差数列分块策略。拿到题先看 check 函数里 cnt_broken==2 就退出的条件，再结合 n=6 的小数据手动模拟 guess2 的 w 取值和步长变化，就能快速排除错误选项。

最容易在 guess2 的步长计算上出错：很多人误以为 w 就是 sqrt(n) 取整，其实 w 必须满足 w*(w+1)/2 >= n，这是等差数列求和公式的逆运用。其次，在模拟 n=100 时，t=2 的最坏情况不是直接套用 sqrt(200)≈14，而是要考虑碎在第 14 层后，剩下 86 层用第二颗蛋线性扫描需要 86 次，但题目问的是“最多猜测次数”，即第一颗蛋试探次数 + 第二颗蛋线性扫描次数，这里有个陷阱：当 k=100 时，第一颗蛋在 14 层碎了，第二颗蛋从 1 扫到 13 共 13 次，加上第一次试探 1 次，总共 14 次；但如果 k 很小，比如 k=1，第一颗蛋在 1 层就碎了，第二颗蛋不用扫，总共 1 次。所以 t=2 的最坏情况其实是第一颗蛋试探次数最多的时候，即 w 层，此时第二颗蛋最多扫 w-1 层，总次数 w + (w-1) = 2w-1，当 n=100 时 w=14，总次数 14+13=27？不对，题目给的选项里没有 27，说明我理解错了。重新看 guess2 代码，它先找 w 使 w*(w+1)/2 >= n，然后从 w 开始递减步长，每次 check 一次，如果碎了就在当前区间线性扫描。对于 n=100，w=14，第一次 check(14)，如果碎了，就在 1-13 线性扫描，最多 13 次，加上第一次 1 次，共 14 次。如果没碎，继续 check(14+13=27)，碎了就在 15-26 扫描，最多 12 次，加上之前 2 次，共 14 次。所以无论怎么碎，最多都是 14 次。这个结论很反直觉，因为很多人以为第一颗蛋试探次数多，第二颗蛋扫描次数也多，加起来会超过 14，但实际上每次碎的时候，第二颗蛋扫描的次数刚好比第一颗蛋试探次数少 1，所以总和恒为 w + (w-1) = 2w-1，当 n=100 时 w=14，2w-1=27？还是不对。哦，我搞混了，题目问的是“最多猜测次数”，即第一颗蛋试探次数 + 第二颗蛋扫描次数，当第一颗蛋在 w 层碎了，第二颗蛋从 1 扫到 w-1，共 w-1 次，加上第一次试探 1 次，共 w 次。当第一颗蛋在 w-1 层碎了，第二颗蛋从 w-(w-1)+1=2 扫到 w-2，共 w-2 次，加上之前 2 次，共 w 次。所以无论怎么碎，总次数都是 w。当 n=100 时 w=14，所以最多 14 次。这个结论很优雅，但很多人会算成 14+13=27，因为误以为每次碎都要重新扫整个区间，其实不是，每次碎只扫当前区间，而当前区间的长度刚好比之前试探次数少 1，所以总和恒为 w。这个点一定要讲清楚。

这道题考查的是扔鸡蛋问题的简化版，核心在于理解 guess1 的线性扫描与 guess2 的等差数列分块策略。拿到题先看 check 函数里 cnt_broken==2 就退出的条件，再结合 n=6 的小数据手动模拟 guess2 的 w 取值和步长变化，就能快速排除错误选项。

概念定义：

• 鸡蛋掉落问题：给定 n 层楼和 k 个鸡蛋，找到临界楼层的最小测试次数。
• 最优策略（2 个鸡蛋）：第一个鸡蛋按 w, w-1, w-2, ... 的步长递增，其中 w 满足 w(w+1)/2 >= n。
• guess1：从 1 到 n 逐个测试，最坏 n 次。
• guess2：先确定起始块大小 w，然后逐块缩减增量，碎了则回退到上一个安全区间线性扫描。

逐步推导：

guess1（线性扫描）

从 1 到 n 逐个测试，最坏 n 次。cnt_broken 最多为 1，因为碎一次后就知道 k 就是当前层，直接 assert_ans 返回，不会继续碎第二个蛋。

guess2（优化策略）

1. 求最小 w 使 w(w+1)/2 >= n 2. 第一步在 w 处测试；不碎则在 w+(w-1) 处测试；依次递减步长 3. 碎了则回退到上一个安全区间线性扫描

最坏情况测试次数 ≈ √(2n)。

判断题解析：

• 22（n=6,k=5）：t=1 猜 5 次，t=2 猜 3 次 → 正确。
• 23（t=2 总 ≤ t=1）：存在边界情况使 t=2 > t=1 吗？通常 t=2 更优，但某些特殊情况下可能相等或更大 → 错误。
• 24（一定会猜中）：两种策略最终都会找到正确结果 → 正确。

选择题解析：

• 25（guess1 中 cnt_broken 最大值）：最多碎 1 次 → 答案 B(1)。
• 26（guess2 最多猜测次数量级）：O(√n) → 答案 C。
• 27（n=100 时最多猜测次数）：t=1 最多 100 次，t=2 最多 14 次 → 答案 A(100,14)。

避坑指南： 注意 cnt_broken 的上限为 2（蛋只有 2 个），但 guess1 中碎 1 次后即找到答案。guess2 的步长计算容易出错，w 必须满足 w*(w+1)/2 >= n，这是等差数列求和公式的逆运用。对于 n=100，w=14，无论怎么碎，总次数都是 14，这个结论很反直觉，但通过模拟可以验证：第一颗蛋在 14 层碎了，第二颗蛋从 1 扫到 13，共 13 次，加上第一次 1 次，共 14 次；第一颗蛋在 13 层碎了，第二颗蛋从 14-13+1=2 扫到 12，共 11 次，加上之前 2 次，共 13 次；以此类推，总次数恒为 14。

技巧总结：2 个鸡蛋 n 层楼的最优策略：第一颗蛋按 √(2n) 递减步长试探，碎了后用第二颗蛋线性扫描。最坏 O(√n)。