2026山西省信息学竞赛真题:二分答案解析

四季读书网 2026-09-16 02:27:31 4 0

2026山西省信息学竞赛真题：二分答案解析

📘 省赛冲刺特训｜2026 年「全国中学生信息学奥林匹克竞赛（山西赛区）」报名已于 9 月 1 日启动、9 月 30 日截止，后续衔接 CSP-J/S 与 NOIP。二分答案是复赛与省赛的高频考点——它把「求最小 / 最大满足条件值」的问题，用「猜测 + 验证」压成 O(N·logS) 的稳解法。今天用一道原创真题拆解它。

一、题目背景

读书节要把 N 本书运到展区，第 i 本书重量为 w[i]。运输必须按书的原始顺序装船，每艘船所载书的重量之和不能超过船的载重 W。组委会最多只能派出 M 艘船。请回答：在所有书都能运完的前提下，船的最小载重 W 是多少？

输入：书的数量 N、最多船数 M、重量数组 w[1..N]；
输出：满足条件的最小整数载重 W；
约定：单本书重量不超过任何合理船载重，且一定能运完。

二、样例

输入：N=5, M=3，重量 w=[4, 8, 1, 5, 6]

输出：11（载重 11 时，3 艘船分别装 [4,8]、[1,5]、[6]，恰好运完；载重 10 时需要 4 艘，不满足）。

三、二分答案思路拆解

核心观察：船载重 W 越大，所需船数越少——这是典型的单调性。于是我们不必逐个试 W，而是：

定上下界
：下界 L = max(w)（单本书至少得装下），上界 R = sum(w)（极端情况 1 艘船全装）；
写判定函数ok(W)
：贪心顺次装船，当前船加下一本书不超 W 就装，否则开新船；统计船数是否 ≤ M；
二分
：当 ok(mid) 为真，说明 mid 可能偏大，令 R = mid；否则令 L = mid+1；直到 L==R 即为最小可行载重。

四、C++ 参考代码

#include <iostream> #include <vector> using namespace std; // 判定：载重 W 时，能否用不超过 M 艘船运完 bool ok(const vector<long long>& w, int M, long long W) { int ships = 1; long long load = 0; for (long long x : w) { if (load + x > W) { // 当前船装不下，开新船 ships++; load = x; if (ships > M) return false; } else { load += x; } } return true; } int main() { int n, M; if (!(cin >> n >> M)) return 0; vector<long long> w(n); long long L = 0, R = 0; for (int i = 0; i < n; i++) { cin >> w[i]; if (w[i] > L) L = w[i]; // 下界：最重的单本书 R += w[i]; // 上界：全部重量之和 } while (L < R) { // 二分答案 long long mid = L + (R - L) / 2; if (ok(w, M, mid)) R = mid; else L = mid + 1; } cout << L << endl; // L == R 即最小可行载重 return 0; }

五、Python 参考代码

def ok(w, M, W): ships, load = 1, 0 for x in w: if load + x > W: # 当前船装不下，开新船 ships += 1 load = x if ships > M: return False else: load += x return True def solve(w, M): L = max(w) # 下界：最重的单本书 R = sum(w) # 上界：全部重量之和 while L < R: # 二分答案 mid = (L + R) // 2 if ok(w, M, mid): R = mid else: L = mid + 1 return L # L == R 即最小可行载重 # 样例 print(solve([4, 8, 1, 5, 6], 3)) # -> 11