这道题我在XTUOJ上刷到的时候第一反应是制药跟二分法有什么关系。真做进去才发现这就是典型的二分答案题背景换成制药厂核心还是那个老套路求一个满足条件的最小值。这篇文章我就拿这道题当引子把二分答案的完整思路、check函数怎么写、边界怎么卡、会踩哪些坑一次性讲透。1. 制药的题意重述从题目描述到算法模型先说一句实话OJ上很多题目的背景故事都写得花里胡哨真正常住考试的只有一句话。这道制药题我按最常见的版本给大家还原一下你在XTUOJ上看到的原题本质上不会跑出这个框架。1.1 原题场景还原某制药厂有一批紧急订单需要在最短时间内生产至少m瓶药剂。厂里有n台反应釜第i台反应釜每生产一个批次的药剂需要t[i]个小时一个批次能产出c[i]瓶。所有反应釜可以同时开启每台反应釜做完一个批次立刻开始下一个批次中间不休息。现在问最少需要多少小时才能让总产量达到m瓶这个描述其实是很多二分答案题的通用皮套。背后那个典型的数学问题是有n台机器机器i生产一件产品需要t[i]小时或者说每个周期耗时t[i]小时、产出c[i]个单位求生产m件产品所需的最短时间。把产品换成药剂把机器换成反应釜题目就从机器生产变成了制药。OJ喜欢这么干目的是考验你在阅读理解之后能不能抽掉壳子看到里面的本质结构。1.2 输入输出样例分析假设输入这样3 100 2 3 3 2 4 5这里第一行是n3台反应釜m100瓶药剂。后面三行分别是每台反应釜的周期时间t[i]和单周期产量c[i]反应釜1每2小时一批每批3瓶反应釜2每3小时一批每批2瓶反应釜3每4小时一批每批5瓶问最少几小时能凑够100瓶我们可以先心算验证一下最终答案应该落在哪个范围。比如给T10小时反应釜1能完成floor(10/2)5批每批3瓶贡献15瓶反应釜2能完成floor(10/3)3批每批2瓶贡献6瓶反应釜3能完成floor(10/4)2批每批5瓶贡献10瓶合计31瓶远不够100瓶。所以答案一定大于10。具体是多少就需要二分来找。1.3 数据范围决定了算法选择这类题目常见的约束是n可以达到10^5甚至更高m可以达到10^9量级t[i]最大可以到10^9。这种数据范围几乎是强制性地告诉你两件事不能模拟。如果从第1小时开始逐小时判断产量最坏情况下要做几百上千亿次运算肯定超时。不能枚举答案。答案的范围太大线性扫描T从1到某个上限同样不可行。唯一合理的方向就是把答案T当作自变量对T做二分搜索。每次用O(n)时间验证某个T是否可行总复杂度是O(n log T_max)稳稳通过。在做任何算法题之前先看数据范围再决定算法模型这个习惯一定要养成。很多同学上来就想着用什么数据结构、什么高级算法其实先看一眼范围能帮你省掉一大半弯路。2. 为什么是二分法单调性论证与错误解法的对比2.1 产量关于时间的单调性二分答案能用的前提是我们搜索的目标函数具有单调性。在这道题里定义函数f(T)表示给定T小时总产量是多少。那么当T增大的时候f(T)是严格不降的。这个结论很直观时间越长每个反应釜能完成的批次数只会越来越多总产量不会减少。用数学语言写f(T) Σ floor(T / t[i]) × c[i]当T1 ≤ T2时floor(T1 / t[i]) ≤ floor(T2 / t[i])所以f(T1) ≤ f(T2)。单调性成立二分的前提就成立了。我们的目标从求最小可行T变成在单调函数f(T)上找第一个使f(T) ≥ m的点。这就是标准的二分答案模型。2.2 直接套公式为什么不行有人可能会想既然总共需要m瓶把每台反应釜的平均每小时产量加起来用m除以这个总速率不就行了吗这个想法错在哪错在整除。反应釜是按整批生产的第3小时结束的时候反应釜1刚好完成1批2小时一批反应釜2差1小时才完成1批。你不能把一个没完成的批次拆成部分产出。所以平均速率算出的T通常会偏小不是真实答案。举个具体例子m10只有一台反应釜t3小时c5瓶。按平均速率算是10/(5/3)6小时看起来6小时应该产出10瓶。但实际上6小时只能完成floor(6/3)2批产出10瓶刚好够。这个例子恰好撞上了。如果把m改为8平均速率算出来是4.8小时向上取整5小时但5小时只能完成1批5瓶不够真实答案是6小时。你看直接公式就在边界上翻车了。2.3 逐小时模拟为什么超时有些基础题允许你从1开始模拟check到第k小时时累加产量。但这种思路放在大数据范围内必死。假如m10^9一台反应釜t1小时、c1瓶那么答案就是10^9小时。逐小时模拟要做10^9次计算每次还要遍历n台设备总操作次数是10^14级别现代CPU也扛不住。而二分只需要log2(10^9)≈30次check每次O(n)总操作量轻松在毫秒级完成。这就是二分法在这个问题里不可替代的根本原因它把线性搜索答案压缩成对数级别搜索答案配合上单调性验证整体复杂度从O(ans×n)降到了O(n log ans)。3. check函数的设计与二分框架核心代码逐行拆解3.1 check函数到底在检查什么二分的每一轮我们猜一个时间mid然后问一个问题在mid小时内总产量能不能达到m瓶能说明mid可能还不够小答案在左边缩小右边界。 不能说明mid太小了答案在右边扩大左边界。这个能与不能的判断就是check函数。它的实现非常直接typedef long long ll; bool check(ll T, ll m, vectorll t, vectorll c) { ll total 0; for (int i 0; i t.size(); i) { total (T / t[i]) * c[i]; if (total m) return true; // 提前退出防溢出 } return false; }注意两点total要开long long。如果所有设备一起算产量轻松超过int上限。循环内一旦total m就立刻返回true不仅省时间还能避免total继续累加导致溢出。3.2 二分区间怎么定左边界很简单最少需要1小时。m如果为0一般题目不会给m0但稳妥起见可以处理答案是0否则从1开始。右边界需要保证一定可行。一个绝对安全的上界是maxTime max(t[i]) × ceil(m / min(c[i]))理解一下最慢的反应釜做一批要max(t[i])小时每批最少产出c_min瓶取所有反应釜中单周期产量最小的那个。如果只用最慢且产量最低这台做完ceil(m / c_min)批需要max(t[i]) × ceil(m / c_min)小时这个时间一定够。所以用它当二分上界一定不会漏答案。更简单的上界也可以直接取max(t[i]) × m。因为即使每批只产1瓶做m批最多也就花max(t[i]) × m小时。数据量大时这个上界可能偏大但只多几次二分迭代完全无伤大雅。3.3 二分循环的写法整数二分最经典的是左闭右闭写法ll left 1; ll right maxT * m; while (left right) { ll mid left (right - left) / 2; if (check(mid, m, t, c)) { right mid; // 可行尝试更小的时间 } else { left mid 1; // 不可行必须往更大的时间找 } } cout left endl;这个写法的关键是当check(mid)为true时right mid而不是right mid - 1。因为mid本身可能已经是答案不能把它丢掉。当check(mid)为false时left mid 1因为mid一定不是答案可以安全排除。用mid left (right - left) / 2而不是(left right) / 2是为了防止left right溢出。这也是一个容易被忽略的细节。3.4 Python版本参考Python写起来更简短适合快速验证思路def check(T, m, times, capacities): total 0 for t, c in zip(times, capacities): total (T // t) * c if total m: return True return False def solve(n, m, times, capacities): left, right 1, max(times) * m while left right: mid (left right) // 2 if check(mid, m, times, capacities): right mid else: left mid 1 return leftPython慢归慢但指数二分的迭代次数非常少配合提前退出中等数据量也能跑。正式比赛里如果Python过不了可以试试PyPy一样的思想速度能快不少。4. 提交时最容易翻车的四个坑边界、溢出、死循环与精度4.1 二分边界写错导致的死循环我在初学二分时最常犯的错误是写成这样while (left right) { mid (left right) / 2; if (check(mid)) left mid; // 错误可能在死循环 else right mid - 1; }当left mid且mid满足条件时如果left和right已经相邻比如left5, right6mid5把left更新成5left没变程序就永远卡在while里。解决方法是严格遵守两条规则当条件成立时收缩的是right找最小值时且right mid当条件不成立时收缩的是left且left mid 1在这类求最小可行值的题里二分方向永远是可行的往左挤不可行的往右推。4.2 long long的使用与提前退出数据范围是题目的第一情报。t[i]和m都可能到10^9乘积更是轻松突破10^18int绝对不够。这种题从一开始就该用long long而不是等发现测试点超限再去改。提前退出不仅是优化更是安全措施。在我4.1给的示例里如果total不做提前退出某个check里累加几次就可能涨到10^18以上一旦溢出变成负数后面的判断逻辑全乱。加一行if (total m) return true;就一劳永逸。4.3 整除时间导致的错误预判整除是这类周期生产问题的灵魂也是最容易让人犯迷糊的地方。比如反应釜周期是7小时给T14小时floor(14/7)2批没问题。但给T13小时floor(13/7)1批剩下6小时什么都干不了。这种时间空窗是隐形的不会在代码里报错但会让你估算的产量偏大。所以check函数里必须用整数除法千万别写成T / t[i]然后期望它自动向下取整。C里正数相除本来就是整除Python里要用//而不是/。用错除法的后果是T13小时时你会算出13/7≈1.857再乘上c产量虚高干扰二分判断。4.4 自测样例清单提交前我建议至少跑这五组数据场景输入期待结果单台设备整除边界n1, m10, t3, c56小时单台设备非整除边界n1, m8, t3, c56小时多台设备同时开工n3, m100, t[2,3,4], c[3,2,5]自行二分验证m非常小n2, m1, t[100,200], c[1,1]100小时选最快周期最慢周期最大上界n1, m10^9, t10^9, c110^18注意溢出第三组是我上面那个样例答案是28小时怎么算的T28时反应釜1产出14批×342瓶反应釜2产出9批×218瓶反应釜3产出7批×535瓶总和95瓶不够。T29时反应釜1产出14×342反应釜2产出9×218反应釜3产出7×535还是95瓶不够。T31时反应釜1产出15×345反应釜2产出10×220反应釜3产出7×535合计100瓶刚好。所以答案是31小时。这个例子告诉你答案并不总是整数倍周期的某个交点必须靠二分慢慢逼近。5. 从制药看一类二分答案题识别套路与举一反三5.1 题型的三个特征刷多了就会发现制药只是二分答案题家族里的一张小脸。它所属的大类有三个特征题目要求一个最小可行值或最大可行值。本题是最小可行时间。可行性与候选值之间呈单调关系。本题是时间越长越可能达标。候选值范围非常大不能线性枚举。识别出这三个特征就可以直接套二分答案框架。很多题说的其实是同一件事只是把药品生产换成零件加工、隧道挖掘、网络传输换汤不换药。刷OJ最忌讳看到新题就慌。先问自己这个题是不是在找一个边界点如果是而且判断一个候选点可行不可行的代价可以接受那八成就是二分。5.2 变形一浮点数二分有些版本会把时间改成实数比如每台反应釜的资料时间是浮点数问你精确到小数点后几位。这时候整数二分不能直接用要改成浮点二分double left 0, right maxT * m; for (int iteration 0; iteration 100; iteration) { double mid (left right) / 2; if (check(mid, ...)) { right mid; } else { left mid; } } printf(%.2f\n, right);浮点二分不需要用while(left right)因为浮点数相等判断很危险。固定迭代100次左右精度绝对够因为每轮迭代区间长度折半100次之后理论误差是2^-100倍早超过题目要求了。浮点二分里同样要注意check函数不能把产量算错。比如T2.5小时周期是1.2小时能完成几批答案是2批因为2.5/1.22.0833向下取整2批。这个向下取整的操作在浮点数里要用floor()函数别直接转int2.0833转int是2没问题但如果恰好是2.999999999999转int就变成1了。稳妥做法是floor(2.99999999 1e-9)或者直接二分出一个答案后再向下/向上微调验证。5.3 变形二求最小化最大值制药是求最小可行时间本质是最小化最大生产周期。翻转一下还有一类题叫最大化最小值比如要在n个位置里选k个使得任意两个选中点之间的最小距离最大。这类题也是二分答案但check函数的方向完全相反检查当最小距离为mid时能不能选出k个点。if条件满足时说明mid还有可能更大所以left mid不满足时说明mid太大了right mid - 1。这就是标准的最大化最小值二分方向跟本文反着记。我给个简单记忆法求最小可行值满足条件就往左收求最大可行值满足条件就往右收。收的时候都要保留当前mid本身作为候选。5.4 学完这道题之后怎么继续练如果你觉得制药掌握了可以按顺序做几个经典二分答案题巩固最小化最大值把一条木棒切分成若干段求满足条件的最短段长。最大化最小值牛棚分栏求牛之间最大可能的最小距离。浮点二分求方程f(x) 0的根要求精度到1e-6。带权二分在制药基础上给每台反应釜加一个启动成本变成在预算内用最短时间完成。前三个是练手感第四个是练模型转换。等你把这几类都做顺了再回头看到制药就会觉得它只是个穿着古装的整数二分题。我个人刷题的习惯是每学一个套路就用它去扫五到十道同类题不做新题只做变形。这样二十道题下来这个套路就长在肌肉记忆里了。XTUOJ这几年出的题风格越来越喜欢穿应用题的壳能一眼剥开壳子看到里面的二分、贪心、DP骨架才是刷题真正磨出来的功夫。