企业官网建设流程全解析

这道题我在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

这里第一行是n=3台反应釜，m=100瓶药剂。后面三行分别是每台反应釜的周期时间t[i]和单周期产量c[i]：

• 反应釜1：每2小时一批，每批3瓶
• 反应釜2：每3小时一批，每批2瓶
• 反应釜3：每4小时一批，每批5瓶

问最少几小时能凑够100瓶？

我们可以先心算验证一下最终答案应该落在哪个范围。比如给T=10小时：

• 反应釜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. 不能模拟。如果从第1小时开始逐小时判断产量，最坏情况下要做几百上千亿次运算，肯定超时。
2. 不能枚举答案。答案的范围太大，线性扫描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通常会偏小，不是真实答案。

举个具体例子：m=10，只有一台反应釜，t=3小时，c=5瓶。按平均速率算是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小时时累加产量。但这种思路放在大数据范围内必死。

假如m=10^9，一台反应釜t=1小时、c=1瓶，那么答案就是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, vector<ll>& t, vector<ll>& 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; }

注意两点：

1. total要开long long。如果所有设备一起算，产量轻松超过int上限。
2. 循环内一旦total >= m就立刻返回true，不仅省时间，还能避免total继续累加导致溢出。

3.2 二分区间怎么定

左边界很简单：最少需要1小时。m如果为0（一般题目不会给m=0，但稳妥起见可以处理），答案是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 left

Python慢归慢，但指数二分的迭代次数非常少，配合提前退出，中等数据量也能跑。正式比赛里如果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已经相邻（比如left=5, right=6），mid=5，把left更新成5，left没变，程序就永远卡在while里。

解决方法是严格遵守两条规则：

• 当条件成立时，收缩的是right（找最小值时），且right = mid
• 当条件不成立时，收缩的是left，且left = mid + 1

在这类"求最小可行值"的题里，二分方向永远是"可行的往左挤，不可行的往右推"。

4.2 long long的使用与提前退出

数据范围是题目的第一情报。t[i]和m都可能到10^9，乘积更是轻松突破10^18，int绝对不够。这种题从一开始就该用long long，而不是等发现测试点超限再去改。

提前退出不仅是优化，更是安全措施。在我4.1给的示例里，如果total不做提前退出，某个check里累加几次就可能涨到10^18以上，一旦溢出变成负数，后面的判断逻辑全乱。加一行if (total >= m) return true;就一劳永逸。

4.3 整除时间导致的错误预判

整除是这类"周期生产"问题的灵魂，也是最容易让人犯迷糊的地方。

比如反应釜周期是7小时，给T=14小时，floor(14/7)=2批，没问题。但给T=13小时，floor(13/7)=1批，剩下6小时什么都干不了。这种时间空窗是隐形的，不会在代码里报错，但会让你估算的产量偏大。

所以check函数里必须用整数除法，千万别写成T / t[i]然后期望它自动向下取整。C++里正数相除本来就是整除，Python里要用//而不是/。用错除法的后果是：T=13小时时你会算出13/7≈1.857，再乘上c，产量虚高，干扰二分判断。

4.4 自测样例清单

提交前我建议至少跑这五组数据：

第三组是我上面那个样例，答案是28小时，怎么算的：T=28时，反应釜1产出14批×3=42瓶，反应釜2产出9批×2=18瓶，反应釜3产出7批×5=35瓶，总和95瓶，不够。T=29时，反应釜1产出14×3=42，反应釜2产出9×2=18，反应釜3产出7×5=35，还是95瓶，不够。T=31时，反应釜1产出15×3=45，反应釜2产出10×2=20，反应釜3产出7×5=35，合计100瓶，刚好。所以答案是31小时。这个例子告诉你，答案并不总是整数倍周期的某个交点，必须靠二分慢慢逼近。

5. 从"制药"看一类二分答案题：识别套路与举一反三

5.1 题型的三个特征

刷多了就会发现，"制药"只是二分答案题家族里的一张小脸。它所属的大类有三个特征：

1. 题目要求一个最小可行值或最大可行值。本题是"最小可行时间"。
2. 可行性与候选值之间呈单调关系。本题是"时间越长，越可能达标"。
3. 候选值范围非常大，不能线性枚举。

识别出这三个特征，就可以直接套二分答案框架。很多题说的其实是同一件事，只是把"药品生产"换成"零件加工"、"隧道挖掘"、"网络传输"，换汤不换药。

刷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函数不能把产量算错。比如T=2.5小时，周期是1.2小时，能完成几批？答案是2批，因为2.5/1.2=2.0833，向下取整2批。这个向下取整的操作在浮点数里要用floor()函数，别直接转int，2.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 学完这道题之后怎么继续练

如果你觉得"制药"掌握了，可以按顺序做几个经典二分答案题巩固：

1. 最小化最大值：把一条木棒切分成若干段，求满足条件的最短段长。
2. 最大化最小值：牛棚分栏，求牛之间最大可能的最小距离。
3. 浮点二分：求方程f(x) = 0的根，要求精度到1e-6。
4. 带权二分：在"制药"基础上，给每台反应釜加一个启动成本，变成"在预算内用最短时间完成"。

前三个是练手感，第四个是练模型转换。等你把这几类都做顺了，再回头看到"制药"，就会觉得它只是个穿着古装的整数二分题。

我个人刷题的习惯是：每学一个套路，就用它去扫五到十道同类题，不做新题，只做变形。这样二十道题下来，这个套路就长在肌肉记忆里了。XTUOJ这几年出的题风格越来越喜欢穿"应用题"的壳，能一眼剥开壳子看到里面的二分、贪心、DP骨架，才是刷题真正磨出来的功夫。