算法竞赛高频考点「二分答案」：一道夏令营分批上机题吃透最小化最大值

面向青少年算法竞赛备赛的原创题解。本篇锚定上海市计算机学会主办的青少年算法竞赛网络月赛甲乙丙三组每月一场、线上作答、免报名费围绕其中出现频率极高的一类考点——二分答案用一道自编题把「最小化最大值」这个模型彻底讲透。一、为什么要专门练「二分答案」很多同学第一次见到二分都停留在「有序数组里查一个数」。但真正在比赛里拉开分差的是另一种用法答案本身具有单调性时直接对答案二分。它的典型信号是这样的题面表述求「最大值的最小值」最小化瓶颈求「最小值的最大值」最大化下限求「最少需要多少个 / 最多能分几组」且这个数量随某个阈值单调变化一旦识别出这类信号题目就从「不知道怎么构造最优方案」的难题变成了「写一个判定函数」的模板题。这个思维转换是小学高年级到初中组选手最值得投资的一块能力。二、原创题目夏令营分批上机题目描述某编程夏令营有n个小组在机房门口按顺序排队第i个小组有a[i]名学员。机房要把这些小组分成若干批上机规则如下队伍不能重新排序每一批必须是队列中连续的若干个小组每个小组不能被拆开必须整组进同一批最多只能安排k批可以少于k批机房容量为X意味着每一批的学员总人数不能超过X。现在要采购机房座位请你求出满足上述条件的最小容量X。输入格式第一行两个整数n和k。第二行n个正整数a[1] … a[n]。输出格式一个整数表示最小容量。样例输入7 3 2 3 5 4 6 1 7样例输出10样例解释容量取 10 时可以分成[2,3,5]、[4,6]、[1,7]三批人数分别是 10、10、8都不超过 10恰好用满 3 批。而容量取 9 时无论怎么分都至少需要 4 批[2,3]、[5,4]、[6,1]、[7]。超过了 3 批的限制所以 9 不可行。数据范围1 ≤ k ≤ n ≤ 10^51 ≤ a[i] ≤ 10^9。三、核心考点拆解这道题一共考四个点每个点都是常考内容考点在本题中的体现答案单调性判断容量越大越容易分完「可行」是单调的二分答案框架在[max(a), sum(a)]上二分容量贪心判定用一次线性扫描算出「容量为 X 时最少要几批」边界与数据类型下界必须是最大单组人数总和会超出 32 位整数关键推理为什么答案单调设f(X)表示容量为X时最少需要的批数。容量变大原来的分法一定仍然合法所以f(X)随X增大单调不增。于是「f(X) ≤ k是否成立」这个布尔值一定是形如不行 不行 不行 行 行 行的形态。我们要找的就是这条分界线上第一个「行」。这正是二分的用武之地。拿样例算一遍把单调性看得更直观容量 X78910111428最少批数 f(X)5543321是否满足 ≤3✗✗✗✓✓✓✓分界线正好落在 10与样例输出一致。四、解法推进从暴力到二分思路一枚举容量会超时从max(a)开始一个一个往上试每次算f(X)。当a[i]最大到10^9时容量的取值范围极大逐个枚举必然超时。但这一步不能跳过——正是枚举过程让我们发现了单调性。思路二把枚举换成二分正解二分的区间怎么定是本题第一个易错点下界lo max(a[i])容量比最大的那一组还小那一组永远装不进去无解上界hi sum(a[i])容量等于总人数一批就够了必然可行。区间内一定存在答案于是可以放心二分。判定函数怎么写贪心即最优给定容量X求最少批数的策略非常朴素从左往右扫能塞就塞塞不下就开新的一批。为什么这样贪心是对的因为每一批装得越靠后越好——如果某一批提前结束后面的负担只会更重批数不可能变少。所以这个「尽量装满」的扫描得到的就是最少批数。C 参考实现#include bits/stdc.h using namespace std; int n; long long k; vectorlong long a; // 容量为 X 时最少需要几批 long long need(long long X) { long long cnt 1, cur 0; for (int i 0; i n; i) { if (cur a[i] X) cur a[i]; else { cnt; cur a[i]; } } return cnt; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n k; a.resize(n); long long lo 0, hi 0; for (int i 0; i n; i) { cin a[i]; lo max(lo, a[i]); // 下界最大单组人数 hi a[i]; // 上界全部人数总和 } while (lo hi) { // 二分「第一个可行的容量」 long long mid lo (hi - lo) / 2; if (need(mid) k) hi mid; // 可行答案在左半边含 mid else lo mid 1; // 不可行答案在右半边 } cout lo \n; return 0; }Python 参考实现import sys def main(): data sys.stdin.read().split() n, k int(data[0]), int(data[1]) a list(map(int, data[2:2 n])) def need(x): 容量为 x 时最少需要几批 cnt, cur 1, 0 for v in a: if cur v x: cur v else: cnt 1 cur v return cnt lo, hi max(a), sum(a) while lo hi: mid (lo hi) // 2 if need(mid) k: hi mid else: lo mid 1 print(lo) main()复杂度分析时间复杂度O(n log S)其中S sum(a)。判定一次是O(n)二分次数约log S ≈ 47次S最大约10^14。总量在10^5 × 47 ≈ 5×10^6级别轻松通过。空间复杂度O(n)只存输入数组。作为对照如果用区间划分的动态规划dp[j][i]表示前i组分成j批的最优瓶颈朴素实现是O(k n^2)在n 10^5时完全不可行。这也说明二分答案不只是「另一种写法」而是量级上的胜出。五、五个高频易错点下界写成 1 或 0。若lo小于max(a)判定函数里会出现「单组永远塞不进」的情况need返回值会失真二分可能收敛到错误答案。判定函数初始cnt写成 0。第一批一开始就存在cnt必须从 1 起算否则整体少算一批结果偏小。忘记开 64 位整数。a[i]到10^9、n到10^5总和最大10^14C 里必须用long long用int会溢出成负数。二分写法混用导致死循环。本题求「第一个可行值」配套写法必须是hi mid与lo mid 1若误写成hi mid - 1又用lo hi会丢解或死循环。取中点用lo (hi - lo) / 2更稳妥。判定条件写成 k。题目允许「少于k批」条件应为need(mid) k写成等号会漏掉大量可行容量。六、进阶练习三个变式掌握模板之后建议按顺序挑战下面三个变式它们都是同一模型的常见包装变式一最大化最小值。把机房容量换成「每批至少多少人才算开班成功且必须正好分成k批求这个下限的最大值」。此时判定函数改为「按容量下限贪心切分最多能切出几批」可行方向翻转为cnt k。二分方向也要跟着改成求「最后一个可行值」。变式二加上运行时间权重。每组除人数外还有一个上机时长要求「每批总时长不超过T的前提下最小化批数」。这时二分对象换成批数或时长判定仍是一次线性贪心练的是「二分谁」这个决策。变式三允许打乱顺序。一旦去掉「必须连续」的限制问题就变成经典的装箱问题NP 困难贪心不再保证最优。这个对比非常重要——二分答案能奏效的前提是判定函数可以在多项式时间内精确求解。理解了这条边界就不会在赛场上错误套用模板。自测清单能不能在 3 分钟内说清「为什么容量越大批数越少」手写判定函数时cnt的初值和cur的重置位置有没有想清楚遇到「最小化最大值」的题面能不能立刻反应出二分的上下界该取什么七、小结与互动二分答案的价值在于把「构造最优解」转成「验证某个解可行」。后者往往简单得多通常一次贪心扫描就能搞定。识别信号最大值最小化 / 最小值最大化、确定单调性、设计判定函数、选对二分写法——这四步走通这一大类题就都在射程内了。本题的完整思路已验证样例答案为 10随机数据与动态规划暴力解对拍一致。建议你先自己独立写一遍再对照上面的实现查漏。你在练二分答案时踩过哪个坑是边界写错、死循环还是判定函数的贪心方向想反了欢迎在评论区留下你的踩坑经历也可以把变式一的判定函数写在评论里我来帮你看正确性。 免费少儿编程资料夸克网盘领取以下资料来自夸克网盘分享点击链接可直接保存若需在 App 内打开也可复制下方明文链接全国青少年信息素养大赛复赛集训题目PythonC.docxhttps://pan.quark.cn/s/93995d3cb1502024信息素养-智能算法应用挑战赛-复赛初中组题目7月7日.pdfhttps://pan.quark.cn/s/da97b5dbf75dPython背记手册.pdfhttps://pan.quark.cn/s/7568ae9ca92bPython课程https://pan.quark.cn/s/a94bf02d00c62024信息素养大赛图形化复赛集训题答案3-9https://pan.quark.cn/s/6ccab7ec3cbc2025年03月份电子学会考级真题https://pan.quark.cn/s/4403c42289122025全国青少年信息素养大赛赛项说明https://pan.quark.cn/s/d9d0df4a9f29青少儿信息素养大赛编程资料https://pan.quark.cn/s/4ab6bd83be8a资料持续更新关注获取最新分享。