GESP 五级 · GESP202609 C++ 五级 第 10 题

小杨需要把若干箱货物按原顺序分配到 days 天中，每天运输连续的若干箱，求能够完成任务的最小载重 量。函数 check(cap) 判断载重量为 cap 时能否在规定天数内运完。横线处应填写（　　）。

long long l = maxWeight;
long long r = totalWeight;
while (l < r) {
long long mid = l + (r - l) / 2;
if (check(mid)) {
____________________
} else {
____________________
}
}
cout << l;

看到 check(mid) 判断，立刻想到二分答案。l 是下界，r 是上界，mid 是中间值。check(mid) 为真说明 mid 可行，但可能还有更小的可行值，要把上界缩到 mid；为假说明 mid 太小，下界要跳到 mid+1。

1. 考纲定位

本题考查 GESP 五级算法模块的二分查找，具体是"答案空间二分"变体。命题人卡住的是学生不会处理"答案空间二分"的边界收缩——这是五级到六级最常见的断层点。

2. 解题思维

看到 check(mid) 判断，立刻想到二分答案。l 是下界，r 是上界，mid 是中间值。check(mid) 为真说明 mid 可行，但可能还有更小的可行值，要把上界缩到 mid；为假说明 mid 太小，下界要跳到 mid+1。