最近在XTUOJ上刷题看到一道标题叫“制药”的二分练习题目名挺有意思点进去一读发现是典型的二分答案入门题。刚好最近不少学弟学妹在问二分法该怎么练我觉得这道题很适合拿来当切入点它短小、判定函数清晰、又有几个容易踩的坑能把二分答案的基本套路讲明白。这篇文章我就以这道题为例从题面拆解、判定函数构造、代码实现到坑点排查完整过一遍刷过类似题比如 POJ 3104 那类“烘干衣服”的同学会发现它们其实是同一个模型。如果你正在准备学校的机试、考研复试上机或者刚开始刷 OJ 想搞懂二分法到底怎么用这篇应该能帮你把“二分答案”这个套路串起来。我不打算写得像题解那样只丢个代码而是尽量讲清楚每一步为什么这么做这样你下次遇到题目换了个马甲也能认出来。1. 先读懂题目制药场景到底在问什么1.1 题面还原XTUOJ 这道“制药”题题面大概是这样的不同 OJ 上文字描述略有差异核心模型一致实验室里有 n 瓶药液第 i 瓶药液当前的杂质含量是 a[i] 毫克目标是把所有药瓶的杂质全部降为 0。净化过程有两种机制自然降解每过一分钟所有药瓶的杂质都会自动减少 1 毫克强力净化每分钟可以额外选择某一瓶药液给它加入一种净化剂。加了净化剂的这一分钟这瓶药液不进行自然降解而是直接被净化掉 k 毫克杂质。现在问你最少需要多少分钟才能让所有药瓶里的杂质都降为 0。输入一般是多组数据每组先给 n 和 k再给 n 个数表示 a[i]n 的范围通常到 1e5 级别a[i] 可能到 1e9。所以不仅要算法正确还得保证复杂度能扛住大数据。我第一次读完题面第一反应是这怎么模拟每分钟要决策给哪瓶药加净化剂加了这瓶下分钟又怎么变化状态空间太大了根本不可能直接递推。但如果你对二分答案有经验看到“最少需要多少分钟”这种问法就应该敏感起来——这极大概率是个二分答案题。1.2 为什么是“二分答案”而不是“二分查找”很多初学者一听到“二分”就想到在有序数组里找一个数也就是经典的二分查找。但算法竞赛里更常用的其实是以二分作为外层框架去猜一个“答案”然后用 O(n) 的判定函数去验证这个答案是否可行。这种思路叫二分答案。两者的区别很关键。二分查找是对已知数组做索引收缩数组本身是给定的二分答案则是我们根本不知道答案但知道答案一定落在一个范围内就在这个范围里不断猜猜完用判定函数验证。制药题能这么做是因为“时间”天然满足单调性如果给你 T 分钟能完成全部净化那么给你 T1 分钟更没问题如果 T 分钟完不成那 T-1 分钟更不可能。有了这个单调性我们就能把问题从“求最小时间”转换成反复问“给定一个时间 T能不能完成”——能就往小猜不能就往大猜。这种“答案单调 验证可行”的组合就是二分答案的识别标志。后面第 5 节我会再展开看到哪些提问方式可以优先往这想。2. 核心思路可行性函数才是二分答案的命门2.1 先把问题转成“给定时间够不够”二分答案的外壳都是同一个模板真正的难点在 check 函数怎么写。制药题的 check(T) 意思是如果只给我 T 分钟我能否把所有药瓶的杂质降到 0要回答这个“能否”不能真的去模拟每分钟怎么操作那太复杂了。我们需要做一个贪心的统计。想一想T 分钟内不管我用不用净化剂每一瓶药液在这一分钟内都会面临两种状态要么自然降解那该瓶减少 1 毫克要么被选中加净化剂那该瓶被净化 k 毫克但不再享受自然降解的 1 毫克。于是T 分钟后如果某瓶药液从头到尾都没被加过净化剂它最多能自然降解 T 毫克。所以如果 a[i] T这一瓶不用操心光靠自然降解就已经达标了如果 a[i] T那这瓶光靠自然降解不够还差 a[i] - T 毫克这部分必须靠净化剂来处理。这就是把“最短时间”转成“给定 T 后每瓶药需要额外处理多少”的过程。2.2 判定函数怎么算一次净化剂到底降多少很多人在这个细节上翻车。题目说的是加了净化剂的那一分钟这瓶药不自然降解而是直接被净化 k 毫克。但注意如果这瓶药这一分钟没有被加净化剂它本来是可以自然降解 1 毫克的。所以当你给它加了一次净化剂相对于“什么也不做”的状态这瓶药多减少的量并不是 k而是 k-1。换句话说在 T 分钟内任何一瓶药都有 T 个“时间单位”可以用。你拿出来一个单位给它加净化剂得到的净效果是 k-1 毫克额外净化。于是如果这个瓶子还差 d a[i] - T 毫克需要处理它需要被加净化剂的次数就是ceil(d / (k - 1))即向上取整。为什么要取整因为只要还剩一点杂质没降到目标就必须再来一次净化剂哪怕这次只用了净化剂一部分效果。到这里check(T) 的流程就清楚了遍历所有药瓶统计总共需要的净化剂次数 sum如果 sum T说明 T 分钟内净化剂够用返回可行否则返回不可行。这里顺手要处理一个特殊边界如果 k 1那 k-1 0每次净化剂的净效果是 0等于白加。这种情况下答案就是 max(a[i])因为只能靠自然降解慢慢把所有药瓶降到 0所需时间就是最大杂质含量。不特判的话check 函数里会出现除零错误。为了验证这个思路拿一组小数据手算一下。假设 n3k3a [2, 5, 8]。如果 T3自然降解 3 毫克后三瓶分别还需要 0、2、5 毫克每次净化剂净效果是 2所以需要的净化剂次数是 0 ceil(2/2) ceil(5/2) 1 3 4 次但 T3只有 3 次机会不够说明 3 分钟不行。如果 T4三瓶分别还差 0、1、4 毫克计算得到 0 ceil(1/2) ceil(4/2) 1 2 3 次而 T44 分钟里有 3 次净化机会够用可行。所以最小时间是 4。这就是判定函数的完整逻辑。能看到check 函数不关心具体哪一分钟对哪瓶药操作只在乎统计出的净化剂总次数是否不超过 T。这个贪心成立的原因在于净化剂可以加在不同药瓶上操作之间没有顺序依赖只要总数不超过总时间就一定可以排出一个合法的操作方案。3. 完整代码与边界处理3.1 可AC的参考代码模板用起来二分范围是 0 到 max(a[i])。上界取 max(a[i]) 是因为就算一瓶净化剂都不用最多等 max(a[i]) 分钟杂质最多的那瓶也能自然降解到 0所以答案不可能超过这个值。C 实现如下#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 100005; ll a[MAXN]; int n; ll k; bool check(ll T) { if (T 0) return false; ll needTimes 0; for (int i 0; i n; i) { if (a[i] T) { ll d a[i] - T; ll times (d k - 2) / (k - 1); // ceil(d / (k-1)) needTimes times; if (needTimes T) return false; // 提前剪枝 } } return needTimes T; } int main() { ios::sync_with_stdio(false); cin.tie(0); while (cin n k) { ll maxA 0; for (int i 0; i n; i) { cin a[i]; if (a[i] maxA) maxA a[i]; } if (k 1) { cout maxA \n; continue; } ll l 0, r maxA; while (l r) { ll mid (l r) 1; if (check(mid)) { r mid; } else { l mid 1; } } cout l \n; } return 0; }代码里需要注意几个点。第一a[i] 和 k 都可能很大统计 needTimes 时用 long long否则极容易溢出。第二t 和 k 都用 ll 类型因为二分 mid 在极端情况也会达到 1e9 级别。第三(d k - 2) / (k - 1) 这个写法是在做向上取整。不要图省事写成 (d k - 1) / k 那种公式这里分母是 k-1不是 k很多人在这里写错导致答案差一。另外while (cin n k) 处理多组输入是 OJ 常见写法XTUOJ 这类平台基本都有多组数据所以必须用 EOF 形式读入。如果写成单组输入直接 return遇到多组数据会只跑一遍就结束WA 都是轻的有些题甚至直接导致答案全错。3.2 二分边界与模板选择二分答案的模板很多人纠结其实核心就两套别混搭l r 型mid 偏向左边也就是 mid (l r) 1。check(mid) 为 true 时 r mid为 false 时 l mid 1。循环结束后答案在 l。这套模板适合求“满足条件的最小值”。l r 型mid 也是 (l r) 1为 true 时 r mid - 1为 false 时 l mid 1最后输出 l。我习惯用第一套因为思维负担小l 是“当前还不确定可行”的最小值r 是“已经确定可行”的最小值两者不断逼近。用 l r 模板时有个容易死循环的点如果 mid 算出来等于 l而且 check(l) 为 true那么 r mid 等于 l循环结束没问题但如果 mid 算出来等于 l而 check(l) 为 false那么 l mid 1区间会收缩也没问题。真正会死循环的是那种 mid 被向上取整为 r 的情况所以用 l r 时取 mid (l r) 1 这个下取整写法配合“可行往左收缩”基本不会出错。在这道题里答案可能是 0 吗如果所有药瓶杂质本来就是 0答案是 0。所以二分下界 l 直接取 0不要取 1。虽然大多数数据不会出现全 0但边界数据测试时还是能踩到。4. 实战调试与常见问题4.1 我在实际提交中踩过的坑这道题我第一次提交就 WA 了原因是 k 和 k-1 的计策没理清楚。我在 check 里计算每瓶需要的净化剂次数时用的公式是 ceil((a[i] - T) / k)直接拿 k 当分母。这种写法在样例数据小的时候可能碰巧对比如 k3、需要额外处理 2 毫克那瓶ceil(2/3)1正好也是 1 次看起来没问题。但一旦数据大起来就露馅了比如 k3、需要额外处理 4 毫克实际需要的净化剂次数是 ceil(4/2)2而我按 ceil(4/3)2居然也对。真正区分两者的场景是 d3、k3实际 ceil(3/2)2错误公式 ceil(3/3)1结果相差一次。为什么会差因为给这瓶药加一次净化剂的那个时间单位它放弃了自然降解的 1 毫克。也就是说你以为净化剂一次净了 k 毫克但这是以牺牲自然降解为代价换来的净效果只有 k-1。这一点在题目描述里写得很清楚但做题时很容易被“直接净化 k 毫克”这个措辞带偏。还有一个我印象很深的坑是二分上界。我一开始图省事把 r 直接设成 1e9 这种大数也没错但数据多的时候多跑很多次二分虽然 log 级别差距不大逻辑上却容易让 check 函数里的 T 超过某些药瓶的杂质导致 a[i] - T 出现负数。虽然是判断 if(a[i] T) 才会计算但如果我没写这个判断负数参与向上取整的除法结果就是 0 或负数整个判定逻辑全乱。所以 r 设成 max(a[i]) 不只是省时间还让 check 逻辑更干净。4.2 常见问题速查表问题现象出错原因解决办法答案整体偏大判定函数里净化剂净效果算错用了 k 而不是 k-1每次净化剂的实际净效果是 k-1公式用 ceil(d/(k-1))答案整体偏小二分模板的收缩方向反了求最小可行值时check 通过往左缩 r不通过往右缩 l死循环或超时mid 取法不对区间收缩不了l r 模板用 mid (l r) 1取左中位数大数据下 WA统计次数用了 int溢出计数变量、a[i]、k 全部用 long long运行时错误 / 除零k1 时 k-10未特判特判 k1直接输出 max(a[i])多组数据只跑一次没写 while(cin n k)输入改成 EOF 读入循环处理每组用例这些坑说出来都很小但实际比赛和日常刷题里WA 了好几次找不到原因基本都栽在这种细节上。调试这一类题我个人的建议是先别急着提交拿一组小数据在草稿纸上演算一遍二分的每一步。比如前面举的 n3, k3, a[2,5,8]把 l0, r8第一次 mid4check(4) 为 true所以 r4第二次 mid2check(2) 为 false所以 l3第三次 mid3check(3) 为 false所以 l4循环结束答案 4。手推一遍代码里的问题基本都能暴露出来。5. 从“制药”到一类二分答案题的通法5.1 看到什么条件能想到二分答案制药题刷完最重要的是把这一类题的识别方法沉淀下来。我总结了一套自己的判断流程遇到新题时照着过一遍先看题目问什么。如果问的是“最少时间”、“最少天数”、“最小最大值”、“最多能分配多少”基本就是在暗示二分的答案维度。再看答案是否单调。也就是如果 X 可行X1 是否一定可行或者如果 X 不可行X-1 是否一定不可行。像制药题时间这个维度完全具备单调性很多分配类题目工作量上限也具备单调性。最后看能否写出 check 函数。不一定要求 check 多简单但至少能在 O(n log n) 甚至 O(n) 内完成。如果 check 本身就非常复杂二分下去也未必划算。满足这三条就直接套二分答案的架子确定上下界二分答案写 check完事。这个方法可以应用到一大票题目比如切分数组的最小区间和、派机器人处理任务、分书本、装集装箱等。表面上场景完全不同内核都是“给定一个约束值判断能不能行”。5.2 几道可以接着练的变形方向制药题还有几个常见的变形非常适合拿来巩固第一目标值不是 0而是某个阈值 m。这时 check 里判断 a[i] T m 即可因为自然降解 T 时间后还要小于等于 m。代码改动很小但能加深对判定函数的理解。第二每个药瓶对净化剂使用次数有上限比如“每瓶最多只能用两次净化剂”。这种情况下 check 里中途一旦某个瓶子需要的次数超过上限立刻返回不可行本质是把一个多维度的约束塞进判定逻辑里。第三把 n 个任务分给 m 个工人每个工人连续工作让最大完工时间最小。这类题就是典型的二分答案check 里走一遍贪心统计“在 T 时间内需要几个工人”然后和 m 比较。思路和制药题如出一辙。练完这些变形你会发现二分法并不神秘它本质上是把“求最优”问题转成“验证可行性”问题。制药题提供的是一个特别干净的样例理解了它后面遇到复杂场景也只是在 check 里做更多文章而已。根据我个人刷题的经验二分答案这套东西光看讲解是练不出来的必须自己上手写几道把边界、溢出、单调性这些细节都踩一遍。像制药题这种“标着二分法”的题目就是最好的练手素材。刷完之后建议把判定函数的推倒过程写进自己的笔记里下次遇到类似模型直接照猫画虎能省不少时间。最后再分享一个小技巧写任何二分答案题都先单独写 check 函数并用极端数据验证。比如全是最小值、全是最大值、k1 的情况、n1 的情况。这些边界数据过一遍代码的稳定性会上升一个档次。这道制药题检验下来整体思路清晰实现也干净用来入门二分法确实挺合适。