P5844 对应的是 IOI 2011 的 Ricehub中文群里一般叫“米仓”或“稻米仓库”。我刷这道题的时候洛谷上标记的是提高/省选难度一眼看上去似乎就是套个二分答案结果真写起来发现 check 函数比你想象的要狡猾得多。如果你已经掌握二分查找但对“如何把最小化半径转成可行性判断”还没完全吃透这篇文章适合你慢慢看。我会把从题目抽象、check 函数推导、C 完整实现到常见翻车点全部讲清楚。1. 先把 Ricehub 的题目还原成标准输入输出1.1 题目背景到底说了什么IOI 2011 的原题背景大概是这样的一条笔直公路从坐标 0 延伸到坐标 L公路旁边分布着 N 片稻田。每片稻田有一个整数坐标位置 x[i]同时有一个产量 b[i]表示这片稻田能产出多少大米。现在政府要在这条公路的某个位置修建一座米仓用来收集一定范围内的大米。问题是运输半径 R 有限制只有距离米仓不超过 R 的稻田才有办法把大米运过去。要求是最终收集到的水稻总量至少是 M你在所有可能的米仓位置里选择使得 R 尽量小。最后输出这个最小的 R。这里有两个容易忽略的细节。第一米仓的位置不是一个给定的候选点而是可以选在道路上的任意实数坐标甚至不一定是某片稻田的位置。第二R 本身只要求是整数程序里我们通常二分这个整数 R。1.2 输入输出格式和自造样例标准输入一般是第一行N、M、L即稻田数、目标水稻总量、道路长度第二行N 个整数表示每片稻田的位置 x[i]第三行N 个整数表示每片稻田的产量 b[i]。输出一行一个整数表示最小可行半径。为了后面讲思路方便我用一组自己构造的数据5 10 20 2 4 7 11 18 3 5 4 8 6现在非常粗鲁地看看答案若 R 2选米仓在坐标 9那么位置 7产量 4和位置 11产量 8都在距离 2 以内总产量 12达到了 M10所以 R2 可行。若 R1任何一片田最多只能和它相邻的一片田搭配两个相邻稻田的距离如果超过 2 就没办法同时覆盖单点最大产量是 8够不到 10所以 R1 不行。最小半径就是 2。为什么要造这个样例因为它能很直观地区分“跨度”和“半径”的关系一片连续区间 [x[l], x[r]] 能被半径 R 覆盖等价于 x[r]-x[l] ≤ 2R。这个关系是整个题的灵魂。2. 第一层转化把“找出最小 R”改为“判断某个 R 是否可行”2.1 暴力做法为什么不可行如果真按题意暴力做你会想到枚举米仓位置枚举半径再把稻田拉进来求和。米仓位置是实数根本没法逐个枚举就算只枚举整数点复杂度也是 O(L·N)L 可以到 10^9 这个级别直接爆炸。正确的思路是答案 R 具有单调性。如果半径 R 可以满足 M那半径 R1 也一定可以满足因为你只是把米仓的覆盖范围变大了。所以问题自然转化为二分答案对每个猜测的 R判断是否存在一个米仓位置能使覆盖到的稻田总产量 ≥ M。于是核心工作落到一个 check(R) 函数上。这个函数的输入是一个整数 R输出布尔值表示“半径 R 是否可行”。2.2 关键观察连续稻田区间可以整体覆盖这里需要想明白一个几何直觉。米仓无论放在哪里只要两块稻田与米仓的距离都不超过 R那么这两块稻田之间的距离上限就是 2R。反过来如果有一块连续稻田从第 l 片到第 r 片最远的两片距离不超过 2R那么我把米仓放在 x[l] 和 x[r] 的中点中间每一片稻田到这个中点的距离都不会超过 (x[r]-x[l])/2自然也就都小于等于 R。所以 check(R) 并不需要真的枚举米仓位置只需要寻找是否存在一个连续区间 [l, r]满足同时满足两个条件x[r] - x[l] ≤ 2R这个区间内所有稻田产量之和 ≥ M。为什么一定是连续区间如果某个最优位置覆盖了一批不相邻的稻田那我完全可以把它们之间的稻田也加进来。加进来的稻田只会让总产量变大不会破坏“都在半径内”的性质。因此最优情况下一定存在一个连续区间包含被覆盖的所有稻田并且条件只会更好。这一步是最容易卡住新手的地方。我当初花了很长时间试图枚举“米仓位置 左右边界”把简单问题复杂化了。实际上只要把米仓位置替换成“区间跨度”所有问题都收束到一个滑动窗口判定上。3. 写 check 函数滑动窗口如何一条龙完成判断3.1 窗口的移动逻辑假设坐标数组 x 已经排好序产量数组 b 和 x 绑定。check(R) 只需要用两个指针维护当前窗口右指针 r 逐一往前扩展每加入一片稻田就把它的产量加进 sum左指针 l 不断收缩直到 x[r] - x[l] ≤ 2R 为止每次窗口合法后看 sum 是否已经 ≥ M如果是return true。这个过程是典型的“右端固定、左端尽量向右挤”的滑动窗口。你可能会有疑问窗口合法后产量不足那再往右扩展一个 r 会更远会不会漏掉夹在中间的更优窗口不会因为循环里左指针已经缩到最短任何一个包含当前 r 且更短的区间只会更早结束产量只会更小。当前 r 对应的产量最大窗口就是 [l, r]如果它都不够那以 r 为右端点的其他窗口更不可能够。伪代码大概长这样bool can(int R) { long long sum 0; int l 0; for (int r 0; r N; r) { sum b[r]; while (x[r] - x[l] 2 * R) { sum - b[l]; l; } if (sum M) return true; } return false; }3.2 我踩过的第一个坑区间跨度写成 R 而不是 2R这个坑我到现在都记得。第一次写的时候我把 while 条件写成了 x[r] - x[l] R然后样例过不去。原因就是没想清楚覆盖关系米仓在区间中间左右两侧都能覆盖 R所以整段跨度可以达到 2R而不是 R。你可以用一个反例验证两个点分别在 0 和 10R5把米仓放在 5两片田都能覆盖但跨度是 10。如果我误用“跨度 ≤ R”就会把这种情况漏判。二分答案题里check 函数里每一条不等式都必须建立在你对几何关系的严格推导之上否则后面全是白搭。3.3 前缀和与滑动窗口的对比也有人习惯用前缀和加二分写 check固定左端点二分出最后一个满足跨度的右端点再查询区间和。这样单次 check 是 O(N log N)乘上二分答案的 O(log L)对于 N10^5 也能过但代码会更绕。滑动窗口每次 check 是 O(N)整体是 O(N log L)更干净也更稳。从原理上看前缀和方案相当于把“窗口收缩”换成了“二分找边界”本质仍然是判断连续区间两者等价。如果对滑动窗口不熟先用前缀和写出正确版本再优化成双指针也是一个很好的学习路径。不过竞赛里我建议直接把滑动窗口写成肌肉记忆因为它的形式非常固定。4. 二分答案的边界与细节我在实测中翻车的地方4.1 二分的上下界怎么定二分下界好说是 0。上界需要注意我直接取了 L。因为道路全长是 L任何一段连续稻田的跨度都不会超过 L所以半径取 L 必然能覆盖所有稻田。如果你把所有稻田的坐标差当成上界也可以但取 L 更简单二分次数也不会多。二分循环我惯用的是左闭右开写法int lo 0, hi L; // 答案在 [lo, hi] 中 while (lo hi) { int mid (lo hi) / 2; if (can(mid)) hi mid; else lo mid 1; } cout lo \n;这里为什么是 hi mid 而不是 hi mid - 1因为 can(mid) 为 true 表示 mid 是一个可行解最小可行解不会比 mid 更大所以上界缩到 mid下界则要移动到 mid 1因为 mid 不可行。4.2 溢出问题2 * R 真的会爆 int这道题我最想提醒你的就是 R 的取值范围。题目里 L 可以到 10^9二分 mid 也会到 10^9 量级那我在 while 条件里写的 2 * R当场就可能超过 32 位 int 的表示范围。虽然有些编译器在 int 乘法溢出后会发生奇怪的回绕程序不一定崩但结果一定错。所以必须写成while (x[r] - x[l] 2LL * R) { ... }只要把 2 换成 long long或者把 x 数组声明成 long long判断就能安全进行。生产环境里我习惯把所有可能乘积的位置全部用 1LL * 保护起来防患于未然。4.3 产量总和要不要 long long产量 b[i] 加起来在极端情况下也可能超过 int。题目如果 N 是 10^5单块田产量可以到 10^9总和就是 10^14int 甚至 long long 的边界都要心里有数。我的建议是b 数组、sum、M 全部用 long long位置数组至少用 long long 参与跨度计算。偷懒只开 int在 IOI 这种级别的题里是非常危险的。4.4 输入坐标不排序怎么办严格来说 IOI 原题给了我按坐标递增排列的稻田但如果你在刷题平台上看到的版本没有保证排序或者你只是从别处拿到数据最好自己排一下。关键是排序时位置和产量要同步移动。我的做法是把 (位置, 产量) 放进 pair然后统一排序再拆开vectorpairint, long long a(N); // 读入位置到 a[i].first产量到 a[i].second sort(a.begin(), a.end());不要只给位置排序结果产量对应错位那就会变成另一个错误百出的方案。我在一次模拟赛里就干过这种事输出样例正确但大数据全错查了二十分钟才发现是排序没有同步。5. 完整 C 实现与实战复盘5.1 一份可以直接提交的代码下面这份代码是我最终提交用的版本去掉了无关输出只保留核心逻辑#include bits/stdc.h using namespace std; int N, M, L; vectorpairlong long, long long farm; // 位置产量 vectorlong long x, b; bool can(long long R) { long long sum 0; int left 0; for (int right 0; right N; right) { sum b[right]; while (x[right] - x[left] 2LL * R) { sum - b[left]; left; } if (sum M) return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin N M L; farm.resize(N); for (int i 0; i N; i) cin farm[i].first; for (int i 0; i N; i) cin farm[i].second; sort(farm.begin(), farm.end()); x.resize(N); b.resize(N); for (int i 0; i N; i) { x[i] farm[i].first; b[i] farm[i].second; } long long lo 0, hi L; while (lo hi) { long long mid (lo hi) / 2; if (can(mid)) hi mid; else lo mid 1; } cout lo \n; return 0; }这份代码有两点额外的封装pair 数组让排序同步long long 覆盖所有边界。如果你在洛谷或其他 OJ 上提交建议把 M 的读入类型对上题目有的平台写的是 int但请用 long long 接受避免流的类型不一致。5.2 我对这道题最深的复盘体会第一次刷这道题时我的 check 函数是这样写的枚举 l 到 r 的所有区间先判断跨度再算总和。虽然逻辑对但 O(N²) 直接超时。后来我意识到这其实就是最长连续子段和的贪心版本只需要维护一个始终合法的窗口就能在 O(N) 内完成。另一个让我记忆深刻的细节是我当时没有把“区间内产量”和“被米仓覆盖的稻田”严格等同起来。总想着米仓应该尽量靠近产量大的几片田结果一度试图对产量排序完全走偏。题目只讨论产量总和没有单块田的“距离加权”所以区间连续性和总产量就足以决定一切。最后我想提一个做题习惯任何二分类题目写完 check 后第一件事是准备一组小数据手动算出答案再拿代码跑。比如我前面构造的 5 块田样例R2 可行、R1 不可行这个检查同时验证了 check 函数的跨度和产量两个逻辑。很多二分题不是难在二分本身而是难在 check 的边界判断上而好的自测样例能把边界问题一把抓出来。这道题之后我对“二分答案 双指针可行性判断”这个组合明显熟练了很多。后来又去做了几道类似题套路基本一致先找答案的单调性再把几何约束或区间约束翻译成窗口条件最后用 while 收缩窗口。P5844 的难度不在于代码本身而在于你有没有在一开始就看穿“半径能覆盖的区间跨度是 2R”这个等价关系。看穿之后这道省选级别的题就只是一道热身题了。