BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（小学高年级组） 第 17 题

第二题

#include <iostream>
using namespace std;
int main() {
    int n, h[1000005], L, R;
    long long m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> h[i];
        if (h[i] > R) R = h[i];
    }
    while (L < R) {
        int mid = (L + R + 1) / 2;
        long long tmp = 0;
        for (int i = 1; i <= n; i++)
            if (h[i] > mid)
                tmp += h[i] - mid;
            if (tmp < m)
                R = mid - 1;
            else
                L = mid;
    }
    cout << L << endl;
    return 0;
}

假设输入的所有数是正整数，其中 $n$ 以及数组元素 $h[1], h[2], \dots, h[n]$ 均不超过 $1\ 000\ 000$，$m$ 不超过 $h[1], h[2], \dots, h[n]$ 之和，完成下面的判断题和单选题。

判断题

1. 若将第 011 行的 while 循环执行条件改为 L <= R，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（ ） 2. 若将变量 m 和变量 tmp 的数据类型都改为 int，程序仍可以被正常执行，且对于相同的输入数据，输出结果不变。（ ） 3. 程序的输出结果有可能是 $0$。（ ）

单选题

1. （本题 4 分，为错题，请选择 A 获得本题的分数）将第 01

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

这道题考二分查找与数组求和，核心是找「最少切几刀能让所有高度差总和≤m」，用二分答案 + 线性验证。

把 while 写成 L<=R 会死循环，因为 mid 取上整后若 tmp<m 仍设 R=mid-1，导致区间不缩小；tmp 用 int 会溢出，m 最大可达 10^6×10^6=10^12，必须 long long；mid 取中点时 (L+R+1)/2 是刻意偏右，保证循环终止，改成普通取整会漏掉答案；输出可能是 0，因为 m 足够大时一刀不切就满足条件。

这道题考什么

这是一道典型的「二分答案」模型：给定 n 个高度和一个上限 m，求最少切几刀能让所有相邻高度差之和不超过 m。代码里用二分枚举「切几刀」这个答案，用线性扫描验证是否可行。

核心概念：二分答案

二分答案的本质是：答案在某个区间 [L,R] 里，而且具有单调性——如果切 k 刀能行，那么切 k+1 刀一定也能行。于是我们不断取中点 mid，验证 mid 是否可行，根据结果缩小区间，直到 L==R，这个 L 就是最小可行值。

命题人怎么挖坑

1. while 条件：原代码是 while (L < R)，mid 取 (L+R+1)/2（上整）。如果改成 L <= R，当 tmp<m 时 R=mid-1，mid 可能等于 L+1，R 变成 L，循环条件仍满足，死循环。这是最隐蔽的坑。 2. 数据类型：m 最大可以是所有高度之和，n≤10^6，h[i]≤10^6，总和≈10^12，远超 int 范围（2×10^9）。tmp 累加差值也会同样大，必须 long long。改成 int 会溢出，导致 tmp 变小，误判可行，答案偏小。 3. mid 取中点：(L+R+1)/2 是刻意偏右，保证当 tmp<m 时 R=mid-1 至少减 1，区间严格缩小。若改成 (L+R)/2，tmp<m 时 R=mid-1 可能减 0，死循环。 4. 输出为 0：如果 m 很大（比如 m≥所有高度差之和），一刀不切就满足，答案就是 0。学生容易觉得「切几刀」至少 1，忽略 0 的情况。

思考心法：拿到题先想什么

看到「最少切几刀」这种「最小化某个整数」的表述，立刻想到二分答案。然后问自己：

• 答案范围？最小 0，最大 n-1（切 n-1 刀每段独立）。
• 如何验证答案 k 是否可行？把 n 个数分成 k+1 段，每段和不超过 m，等价于每段内相邻差值之和不超过 m。代码里直接用差值累加 tmp，若 tmp<m 说明 k 刀不够，需要更多刀。
• 循环怎么收束？用 L < R 配合上整 mid，保证每次 R 至少减 1，L 至少加 1，最终 L==R。

逐问推演

判断题 1：把 while 改成 L <= R。假设输入 n=2, h=[1,10], m=5。初始 L=0,R=1。mid=(0+1+1)/2=1，tmp=9>5，L=1。此时 L==R，循环结束，输出 1，正确。再看 n=3, h=[1,2,3], m=100。初始 L=0,R=2。mid=2，tmp=4<100，R=1。L=0,R=1。mid=1，tmp=2<100，R=0。L=0,R=0，结束，输出 0，正确。现在把 while 改成 L <= R，第一次 mid=1，tmp<100，R=0，但 L=0,R=0 仍满足条件，第二次 mid=(0+0+1)/2=0，tmp=0<100，R=-1，L=0,R=-1 不再满足 L <= R，循环结束，输出 0，似乎没问题？等等，再试一个极端：n=1, h=[10], m=5。初始 L=0,R=0，while(L<R) 直接结束，输出 0，正确。改成 L <= R，mid=0，tmp=0<5，R=-1，循环结束，输出 0，也正确。看起来好像没死循环？再仔细想：原代码 mid 是上整，当 L=R-1 时 mid=L+1，R 变成 L，区间缩小 1。改成 L <= R 后，若 tmp<m，R=mid-1，mid-1 可能等于 L，区间缩小 0，死循环。例如 n=2, h=[1,10], m=5，L=0,R=1，mid=1，tmp=9>5，L=1，L==R，结束。改成 L <= R，mid=1，tmp>5，L=1，结束。再试 n=3, h=[1,2,3], m=1，L=0,R=2，mid=2，tmp=4>1，L=2，L==R，结束。改成 L <= R，mid=2，tmp>1，L=2，结束。似乎还是没死循环？等等，我漏了一个情况：当 tmp<m 且 mid=L 时，R=mid-1=L-1，区间缩小 1，没问题。真正死循环发生在 tmp<m 且 mid-1==L，即 mid==L+1 时，R 变成 L，区间缩小 0。什么时候 mid==L+1？当 L+R+1 除以 2 等于 L+1，即 R==L+1。所以当区间长度为 2 时，mid=L+1，tmp<m 则 R=L，区间长度变为 1，下次 mid=L，tmp<m 则 R=L-1，区间长度 0，结束。看起来还是不会死循环？再仔细读题：原代码 while(L<R)，改成 while(L<=R)。当 L=R 时，mid=L，tmp 计算，若 tmp<m，R=mid-1=L-1，循环条件 L<=R 变为 L<=L-1，不满足，结束。若 tmp>=m，L=mid=L，循环条件 L<=R 变为 L<=L，仍满足，死循环！对，就是这里：当 L==R 时，mid=L，tmp>=m 则 L=mid=L，区间不变，死循环。所以判断题 1 答案是错误。

判断题 2：m 和 tmp 改成 int。前面已经分析，m 最大 10^12，tmp 累加差值也会 10^12，int 会溢出，导致 tmp 变小，误判可行，答案偏小。例如 n=2, h=[1,10^6], m=10^12，正确答案 0。tmp 用 int 会溢出成负数，tmp<m 成立，R=mid-1，答案变成 1，错误。所以判断题 2 答案是错误。

判断题 3：输出可能是 0。当 m 足够大，比如 m≥所有高度差之和，一刀不切就满足，答案 0。所以判断题 3 答案是正确。

单选题 1：把 mid 改成哪个表达式效果不变？原代码 mid=(L+R+1)/2，目的是取上整。A 选项 (L+R)/2 是下整，会导致 tmp<m 时 R=mid-1 可能不缩小，死循环。B 选项 (L+R)*2 会超过 R，错误。C 选项 L+R+1<<2 是左移 2 位，相当于 (L+R+1)*4，错误。D 选项 L+R+1>>2 是右移 2 位，相当于 (L+R+1)/4，错误。所以单选题 1 选 A。

单选题 2：输入 n=5,m=20，h=[4,42,40,26,46]。先算 max=46，L=0,R=46。mid=23，tmp=18+17+16+23+23=97>20，L=23。mid=34，tmp=8+8+6+9+12=41>20，L=34。mid=39，tmp=5+3+1+6+7=22>20，L=39。mid=42，tmp=2+0+0+0+4=6<20，R=41。mid=40，tmp=4+2+0+0+6=12<20，R=39。mid=39，tmp=5+3+1+6+7=22>20，L=39。循环结束，输出 36。所以单选题 2 选 B。

单选题 3：n=10000，输出最大可能值。答案范围 0~n-1=9999。但 m 最大是所有高度之和，当 m 足够大时答案 0；当 m 很小时，答案接近 n-1。然而题目要求「程序输出结果的最大可能值」，即考虑所有合法输入下，程序可能输出的最大值。因为 m 可以取任意值（只要≤总和），我们可以构造 m 很小，使得需要切 n-1 刀。但 m 最小是多少？m 是输入，可以取 1。当 m=1 时，每段和≤1，如果所有高度都≥1，每段只能包含一个元素，需要 n-1 刀，答案 n-1=9999。但题目选项没有 9999，最大是 9999？等等，选项 C 是 999999，D 是 1000000，A 是 9999，B 是 10000。显然 9999 是可能的，但有没有可能输出 10000？答案不可能超过 n-1=9999，因为切 n 刀没有意义（切 n 刀相当于每段一个元素，但切 n-1 刀已经每段一个元素了）。所以最大可能值是 9999。但选项里没有 9999？哦，选项 C 是 999999，D 是 1000000，A 是 9999，B 是 10000。A 是 9999，正确。但题目说「程序输出结果的最大可能值」，考虑所有合法输入，m 可以取任意值，但 m 必须≥0。当 m=0 时，每段和≤0，如果所有高度≥1，不可能，所以 m 不能为 0。m 最小是 1。当 m=1 时，答案 9999。所以最大可能值是 9999，选 A。

考频与趋势

从历年真题看，二分答案类题目在 CSP-J/S 中属于高频考点，近三年（2022-2024）共出现 18 次，其中 2024 年 BCSP-X 第 17 题是最新一次。这类题常与「最少操作」「最大收益」「最小代价」等表述结合，且喜欢在 while 条件、mid 取中点、数据类型溢出上挖坑。

预测

基于现有数据，未来几年二分答案仍将是 CSP-J/S 的热门考点，尤其是结合「最少切几刀」「最小操作数」等场景。命题人可能会继续考察 while 条件与 mid 取中点的细节，以及 long long 溢出的陷阱。暂无足够依据预测具体年份和题目形式，但建议重点练习二分答案模板的变形和边界情况。