最近在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 分钟能完成全部净化，那么给你 T+1 分钟更没问题；如果 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 函数里会出现除零错误。
为了验证这个思路，拿一组小数据手算一下。假设 n=3，k=3，a = [2, 5, 8]。如果 T=3，自然降解 3 毫克后，三瓶分别还需要 0、2、5 毫克，每次净化剂净效果是 2，所以需要的净化剂次数是 0 + ceil(2/2) + ceil(5/2) = 1 + 3 = 4 次，但 T=3，只有 3 次机会，不够，说明 3 分钟不行。如果 T=4，三瓶分别还差 0、1、4 毫克，计算得到 0 + ceil(1/2) + ceil(4/2) = 1 + 2 = 3 次，而 T=4，4 分钟里有 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 当分母。这种写法在样例数据小的时候可能碰巧对，比如 k=3、需要额外处理 2 毫克那瓶，ceil(2/3)=1，正好也是 1 次，看起来没问题。但一旦数据大起来就露馅了，比如 k=3、需要额外处理 4 毫克，实际需要的净化剂次数是 ceil(4/2)=2，而我按 ceil(4/3)=2，居然也对。真正区分两者的场景是 d=3、k=3：实际 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 |
| 运行时错误 / 除零 | k=1 时 k-1=0，未特判 | 特判 k==1，直接输出 max(a[i]) |
| 多组数据只跑一次 | 没写 while(cin >> n >> k) | 输入改成 EOF 读入，循环处理每组用例 |
这些坑说出来都很小，但实际比赛和日常刷题里，WA 了好几次找不到原因，基本都栽在这种细节上。
调试这一类题，我个人的建议是：先别急着提交，拿一组小数据在草稿纸上演算一遍二分的每一步。比如前面举的 n=3, k=3, a=[2,5,8]，把 l=0, r=8，第一次 mid=4，check(4) 为 true，所以 r=4；第二次 mid=2，check(2) 为 false，所以 l=3；第三次 mid=3，check(3) 为 false，所以 l=4；循环结束答案 4。手推一遍，代码里的问题基本都能暴露出来。
5. 从“制药”到一类二分答案题的通法
5.1 看到什么条件能想到二分答案
制药题刷完，最重要的是把这一类题的识别方法沉淀下来。我总结了一套自己的判断流程，遇到新题时照着过一遍：
先看题目问什么。如果问的是“最少时间”、“最少天数”、“最小最大值”、“最多能分配多少”，基本就是在暗示二分的答案维度。
再看答案是否单调。也就是如果 X 可行，X+1 是否一定可行，或者如果 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 函数，并用极端数据验证。比如全是最小值、全是最大值、k=1 的情况、n=1 的情况。这些边界数据过一遍，代码的稳定性会上升一个档次。这道制药题检验下来，整体思路清晰，实现也干净，用来入门二分法确实挺合适。
