今天继续打卡信奥刷题正好轮到系列里的第 2941 道P5844对应 IOI 2011 原题 ricehub。很多人看到“IOI 原题”四个字就先虚了一半其实这道题放在如今的省选难度里根本排不上号核心考的就是二分答案、前缀和、再加上一个带权中位数的结论。思路捋顺之后代码不超过 80 行C 实现起来非常清爽。这道题在国内 OJ 上一般叫“米仓”或“粮仓”。题面不算长一条笔直的公路旁有若干块稻田每块稻田有自己的位置和产量你要选一个位置建米仓把稻米集中运过去运输费用等于产量乘以运输距离。现在给一个总预算问最多能让多少块稻田的米都送进同一个米仓。这个问题最适合拿来练习一类经典套路先想办法判断“某一段区间是否可行”再套二分或双指针解决整体最大值。下面我把完整思路和踩坑记录都写出来。1. 先把题意嚼碎它到底让你求什么1.1 题面直译与背景原始题面里公路可以看成一条坐标轴每块稻田 (i) 有一个坐标 (x_i) 和一个产量 (p_i)。你建一个米仓在坐标 (pos)运第 (i) 块稻田的米的成本就是[ p_i \times |x_i - pos| ]总成本就是所有被覆盖的稻田的成本之和。题目给一个预算 (B)问最多能选多少块稻田使得存在一个位置 (pos)让这些稻田的运输总成本不超过 (B)。稻田本身是沿着公路排开的所以输入时 (x_i) 已经按从小到大排好序这一点很关键后面所有前缀和、二分、双指针都建立在这个有序性上。1.2 从生活场景到数学模型我第一次读这题时第一反应是“这跟最大连续子段和有点像”因为输出的答案一定是连续的一段稻田至少最优解可以看成连续段。为什么因为如果选了第 (i) 块和第 (k) 块稻田中间那块稻田就算不选把它加进去也不会让最优费用变差——只会增加覆盖范围却可能因为它的位置帮米仓“居中”而降低其他人的运输距离。更严格地说任何最优方案都可以扩展成连续区间而不增加费用。这个性质记住就好做题时会少想很多弯弯绕。于是问题就变成找一个长度尽可能大的连续区间 ([l, r])并且存在某个 (pos)使得区间内所有稻田的运输成本总和不超过预算。1.3 覆盖类问题的通用观察这种“最多能选多少个”的题目十有八九能二分答案。只要我能快速判断“是否存在长度为 (k) 的连续区间可行”就可以从小到大猜答案。判断函数最多调用 (O(\log n)) 次所以关键就落在给定区间 ([l, r])如何在 (O(\log n)) 甚至 (O(1)) 时间内算出它的最小运输成本。这就是这道题最漂亮的部分。2. 关键性质米仓为什么必须建在带权中位数上2.1 先考虑子问题给定一段稻田建哪里最便宜假设我确定要服务区间 ([l, r])而且不管区间外面的稻田。此时最优建仓位置在哪很多人第一反应是“中点”理由是距离总和最小这个问题在一维数轴上确实是中位数最优。但这里不是纯距离而是“距离乘产量”。每块稻田的重量不一样产量大的稻田对总费用的影响更大米仓自然会偏向产量更重的那一侧。所以正确答案是带权中位数。带权中位数的定义很直观把区间内所有稻田按坐标从左到右排好从左边开始累加产量当累计产量第一次超过区间总产量的一半时停在的那个位置就是带权中位数。2.2 为什么带权中位数最优一个简单的移动证明我用自己的话解释一下这个结论理解了以后代码就不会写错。假设米仓现在放在某个位置 (pos)。如果把米仓向右移动一小段距离 (\delta)那么位于 (pos) 左侧的稻田距离都增加了 (\delta)右侧的稻田距离都减少了 (\delta)。总费用变化大约是[ \delta \times (左边总产量 - 右边总产量) ]这个式子说明了两件事如果左边产量大于右边向右移动会让总费用增加所以应该向左移如果右边产量大于左边向左移动会让总费用增加所以应该向右移只有当左边产量和右边产量都不超过总产量一半时往哪边移都不会让费用变小。换句话说最优位置就是左右两边产量“势均力敌”的点也就是带权中位数。这个证明对理解后面代码里的(W 1) / 2非常有帮助。2.3 用前缀和在 (O(\log n)) 里找到带权中位数现在要在区间 ([l, r]) 里快速找到带权中位数。先预处理两个前缀和数组(S[i] \sum_{t1}^{i} p_t)用来快速求任意区间的总产量(D[i] \sum_{t1}^{i} x_t \times p_t)这是带权坐标前缀和后面算费用要用。区间 ([l, r]) 的总产量是[ W S[r] - S[l-1] ]带权中位数要找的是最小的 (mid)使得[ S[mid] - S[l-1] \ge \frac{W1}{2} ]因为 (S) 数组是单调不减的直接用lower_bound就能找到这个 (mid)。这里的 ((W1)/2) 是 C 整数除法的写法建议直接按这个写不要改成 (W/2)否则产量总和为奇数时容易选出偏左的点结果虽然通常也能过但不严谨。3. 主框架二分答案 前缀和 check 函数3.1 为什么答案可以二分二分答案的前提是可行性单调。也就是说如果存在长度为 (k) 的可行区间那么一定存在长度为 (k-1) 的可行区间。这个很好证明假设 ([l, lk-1]) 是满足预算的区间那么去掉最右边那块稻田得到 ([l, lk-2])运输成本只会更小所以仍然满足预算。所以我可以二分最终答案 (k)每次判断是否存在长度为 (k) 的区间可行时间复杂度 (O(n \log n)) 一次 check总复杂度 (O(n \log^2 n))。(n \le 10^5) 时完全能跑。3.2 check 函数的数学化实现check 里需要枚举区间左端点 (l)右端点 (r l k - 1)然后算这个区间的最小运输成本。最小成本的计算分三步求区间总产量 (W S[r] - S[l-1])用lower_bound找到带权中位数下标 (mid)米仓就放在坐标 (x[mid])用前缀和快速计算总费用。费用具体分成左右两部分。左边部分也就是区间 ([l, mid]) 的稻田都往右运到 (x[mid])费用是[ x[mid] \times (S[mid] - S[l-1]) - (D[mid] - D[l-1]) ]右边部分即区间 ([mid1, r]) 的稻田都往左运到 (x[mid])费用是[ (D[r] - D[mid]) - x[mid] \times (S[r] - S[mid]) ]两部分加起来就是该区间以带权中位数建仓的最小总费用。我一开始写的时候总想把左右部分合并成一个公式后来发现拆开反而更不容易出错。3.3 完整 C 代码与逐段解析下面是我用 C17 写的完整代码亲测能过。#include bits/stdc.h using namespace std; long long n, B; vectorlong long x, p, S, D; // 计算区间 [l, r] 的最小运输成本 long long calc(int l, int r) { long long W S[r] - S[l - 1]; // 找带权中位数累计产量第一次达到 W 的一半以上 int mid lower_bound(S.begin() l, S.begin() r 1, S[l - 1] (W 1) / 2) - S.begin(); long long res x[mid] * (S[mid] - S[l - 1]) - (D[mid] - D[l - 1]); res (D[r] - D[mid]) - x[mid] * (S[r] - S[mid]); return res; } // 判断是否存在长度为 k 的可行区间 bool check(long long k) { for (int i 1; i k - 1 n; i) { if (calc(i, i k - 1) B) return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n B; x.assign(n 1, 0); p.assign(n 1, 0); for (int i 1; i n; i) cin x[i]; for (int i 1; i n; i) cin p[i]; S.assign(n 1, 0); D.assign(n 1, 0); for (int i 1; i n; i) { S[i] S[i - 1] p[i]; D[i] D[i - 1] x[i] * p[i]; } long long lo 0, hi n, ans 0; while (lo hi) { long long mid (lo hi) 1; if (check(mid)) { ans mid; lo mid 1; } else { hi mid - 1; } } cout ans \n; return 0; }注意所有涉及前缀和与费用的变量都用了long long。坐标最大到 (10^9)产量最大到 (10^4)D数组单个值就可能到 (10^{14}) 量级区间费用加起来更是可能接近 (10^{18})不开long long必炸。3.4 复杂度分析数据范围一般是 (n \le 10^5)二分答案需要 (O(\log n)) 轮每轮 check 枚举 (O(n)) 个区间每个区间用lower_bound找中位数是 (O(\log n))所以总复杂度是[ O(n \log^2 n) ]这个复杂度在 (n 10^5) 时是稳妥的。实际运行中check 内部可以提前剪枝一旦找到一个可行区间就立刻返回true常数很小。4. 另一种思路双指针滑动窗口直接扫4.1 窗口费用的单调性二分答案很稳但它其实不是这道题的最优解。因为随着右端点右移、左端点右移窗口的最小费用是有单调性的固定左端点右端点右移时多服务了稻田最小费用只增不减固定右端点左端点右移时少服务了稻田最小费用只减不增。这意味着我可以直接用滑动窗口维护一个“当前费用不超过预算”的窗口右端点一路向右扫一旦费用超了就把左端点右移直到费用重新变合法。遍历结束时过程中出现过的最大窗口长度就是答案。这个性质和“最小覆盖子串”那类问题很像区别在于这里窗口移动后需要重新计算费用而不是维护计数。由于每次计算费用仍要找到带权中位数整体复杂度是 (O(n \log n))比二分答案的 (O(n \log^2 n)) 更优。4.2 双指针实现的细节我写了一个calc(l, r)函数直接复用代码和前面的 check 里几乎一样。双指针部分非常短long long ans 0; int left 1; for (int right 1; right n; right) { while (left right calc(left, right) B) { left; } // 此时 [left, right] 是右端点为 right 时的最长合法窗口 ans max(ans, (long long)right - left 1); }你可能会担心left只向右移动会不会漏掉某些可能更大的窗口不会。因为当calc(left, right) B时对于任意更大的left窗口变小费用只会更小而如果当前窗口合法继续扩大right才是让答案变大的唯一途径。这正是滑动窗口的正确性所在。要注意的是calc(left, right)每次调用都做一次lower_bound时间复杂度 (O(\log n))整体 (O(n \log n))。如果想再优化到严格 (O(n))可以维护一个随左右指针变化的“中位点指针”但那样写起来容易出边界问题实战中 (O(n \log n)) 对 (10^5) 数据已经非常快没必要自找麻烦。4.3 两种算法怎么选两种做法各有适用场景。二分答案的优点是思路直接、扩展性强比如如果题目改成“每块稻田产量还可能变成 0”之类的变体check 逻辑仍然适用双指针的优点是常数小、代码短但依赖窗口费用单调性如果题目改成二维平面上的选址就不一定还能用滑动窗口。我的建议是这道题两种方法都自己实现一遍。二分答案是基础功双指针是进阶技巧都练过以后以后再遇到“最大连续区间 费用限制”的组合脑子里就会同时弹出两条路。5. 实战调参与避坑实录5.1 溢出问题long long 是底线这个坑我踩过。第一次提交时觉得中间结果不会太大用int存前缀和数组样例能过一提交就 WA。原因很简单D[i] x[i] * p[i]其中 (x_i) 最大 (10^9)(p_i) 最大 (10^4)乘积是 (10^{13}) 量级早就超出int范围了。更不用说D[r] - D[l-1]求和之后可能到 (10^{18}) 量级。所以所有涉及坐标乘产量的变量全部用long long。5.2 查找带权中位数时的(W 1) / 2很多新手会纠结为什么不用W / 2。举个例子区间总产量 (W 5)带权中位数要求左边累计产量至少到总产量的一半以上也就是至少 3。C 里(5 1) / 2 3而5 / 2 2后者会让lower_bound选到偏左的位置。虽然这种偏差在最终费用计算中影响不大但数学上不严谨碰到边界数据可能就 WA 了。所以我统一写(W 1) / 2。5.3 对拍验证与调试技巧这种数学味道比较重的题写完后我强烈建议对拍。生成小数据时暴力枚举所有区间、枚举区间内所有坐标作为米仓位置计算最小费用再和calc(l, r)的结果比对。暴力最优位置可以只枚举区间内的稻田坐标因为费用函数是折线极值一定在某个分段点上。long long brute(int l, int r) { long long best LLONG_MAX; for (int posIndex l; posIndex r; posIndex) { long long sum 0; for (int i l; i r; i) { sum abs(x[i] - x[posIndex]) * p[i]; } best min(best, sum); } return best; }随机生成 (n \le 8) 的小数据位置和产量都限定在 (20) 以内多跑几千组如果calc和brute全部一致再提交大数据的把握就很大。5.4 常见错误速查表我把刷这道题时容易犯的错整理成了表格方便以后复习时快速定位。错误现象可能原因排查方法编译报错类型混用位置、产量、费用用了不同整型统一用long long答案比实际小 1二分边界lo 0, hi n写错了或漏判长度为 (n) 的区间用while (lo hi)并分别更新lo mid 1和hi mid - 1随机数据必错calc里中位点下标找错可能越界打印每个区间的l, r, W, mid, cost和暴力结果对比超时check 里没有提前退出找到第一个可行区间就return true边界 RElower_bound的 end 迭代器写成了begin() r区间是 1-indexed必须写begin() r 16. 做完这题后的几点体会6.1 这类“最大化区间长度”题目的通用套路P5844 的最大价值不是它的 IOI 头衔而是它把几个最基础的工具串在了一起单调性判断、前缀和优化、带权中位数的数学结论。这种题以后遇到很多比如“给定数组和一个代价函数求最长子数组使得代价不超过限制”基本思路都是先看代价函数有没有单调性有就用双指针没有就二分答案代价函数本身复杂就用前缀和或预处理优化。6.2 带权中位数的延伸思考带权中位数只在“绝对距离”作为代价函数时才成立。如果题目把运输成本改成距离平方那最优位置就不再是中位数而是加权平均值这对应最小二乘的思想。所以做算法题时每次看到一个结论我都建议想一下“这个结论依赖哪些假设”改掉假设后结论还会不会成立。想明白这一点以后遇到变形题就不会被牵着鼻子走。最后分享一个小经验你如果第一次做这类题不要只抄题解代码。自己花半小时证明一下带权中位数性质、手写一次对拍程序这些时间花得非常值。这题的 AC 只是起点真正带走的是“看到代价函数先想单调性”的做题本能。