XTUOJ湘潭大学OJ上有一道叫“制药”的题题号我记不太清了但只要你搜一下“制药”十有八九会看到它。这道题表面是讲做药、配药材、算库存实际上就是一道非常典型的二分答案题考察的是你能不能从“每天生产多少份”这个数值里找到单调性然后用二分把这个最优值拧出来。我为什么想专门写这篇东西因为我在XTUOJ上看到太多人在这道题上WA到怀疑人生也有不少人问“为什么我暴力模拟超时了”“为什么我用二分也WA了”“check函数到底怎么写”。我当年做这道题的时候也踩过一堆坑今天干脆把这题从题意拆解、思路推导、完整代码到避坑经验一次性讲透。无论你是刚学二分的新手还是已经会二分模板但一到应用题就懵的人这篇应该都能帮到你。顺带说一句最近XTUOJ还搞过类似“世界杯”那种刷题活动很多人平时刷题不少结果一遇到二分应用题还是会卡壳——所以这类基础套路值得认真复盘一遍。1. 题目到底在问什么先拆“制药”的需求边界1.1 常见题面与我的抽象模型这类题在不同年份、不同OJ上细节可能略有出入但核心模型通常长这样药厂要连续生产某种药品一共有 n 种药材第 i 种药材当前库存是 a[i]生产一份药品需要消耗第 i 种药材 need[i] 份。现在要求连续生产 D 天而且每一天的产量必须是一个固定值不能今天生产100份明天生产50份。问你每天都保持同样的产量最大能把日产量定到多少才能在 D 天内不断料。我当年拿到的版本大致就是上面这个意思如果你在别的平台上看到的题目描述略有不同没关系只要你能把题面抽象成“给了一堆库存、一堆单份消耗、一个生产天数求最大日产量”这个框架思路就是通用的。这个模型的关键在于“连续 D 天产量相同”。很多人刚开始会想歪那我是不是可以第一天多产点后面少产点不行题面要求每天产量相同这就把一个偏贪心的问题硬生生变成了一个带约束的最优化问题。你只能选一个日产量 X然后看所有药材在 D 天内够不够用。日产量 X 一旦定下来D 天内第 i 种药材的总消耗量就是 X × need[i] × D。只要对每一种药材 i都满足a[i] X × need[i] × D那么日产量 X 就是可行的。如果某一种药材不够哪怕其他药材堆成山也白搭因为配方是固定的缺一味药就做不出成品。1.2 为什么直接模拟会翻车我第一次看到这道题的时候脑子里冒出来的第一个做法是从 X 1 开始一个个往上试每次都对所有药材做一次检查直到某个 X 不满足条件为止。这个思路不能说错但问题在于效率。假设题面给的数据比较温柔库存上限是 1e9那 X 可能要到 1e9 甚至更大。每次检查要遍历 n 种药材如果 n 又是 1e5那总复杂度就是 1e9 × 1e5 1e14这在OJ上基本是跑到天荒地老。就算数据范围没有这么极端只要答案的数量级一大暴力枚举必然超时。而且暴力枚举还有一个隐藏风险你从 1 开始往上试如果答案本身是 0比如某种药材库存直接为 0一份都做不出来你还要单独处理边界。多一层判断就多一个出错的点。模拟翻车的本质原因是日产量 X 的取值范围是一个连续区间你枚举的是一个个离散值而正确答案可能落在很大很大的值域里。你需要一种能跳过中间无关值、直接锁定向最优解的搜索方式这就是二分法出场的理由。1.3 可行性随产量单调变化二分的理论基石二分的适用前提只有一个单调性。放在这道题里单调性极其直观——如果你每天生产 X 份药品能坚持 D 天不断料那么你把日产量调低到 X-1 份一定也能坚持 D 天反过来如果 X 份药品已经断料了那 X1 份就更不可能够。用生活化的话说产量越高药材消耗越快可行性只会越来越差产量越低日子越好过可行性只会越来越好。所以“可行性”这个属性随着 X 增大会经历一个“可行”到“不可行”的转折点或者反过来说从不可行到可行取决于你二分的角度。我们要找的答案就是分界线上的那个最大可行值。这个性质极其重要因为它让你不需要逐个检查每一个 X。你可以每次直接猜一个中位数看看它可行不可行然后根据结果扔掉一半的搜索区间。这就是二分答案的底层逻辑不直接求答案而是不断试探“这个值行不行”用可行性把答案逼出来。我见过很多人在做题的时候一上来就总想着“怎么直接算出答案”但在这类题里“判断一个值可不可行”往往比“直接求出最优值”简单得多。制药这道题就是典型你很难一眼看出最大日产量是多少但给你任何一个 X你能很轻松地判断它行不行。这就是二分答案的标志性特征。2. 暴力思路到二分思路推导过程逐段展开2.1 先写出暴力才知道二分优化了哪里很多教程喜欢直接甩二分模板我觉得这不是最好的方式。我自己习惯先把暴力想清楚因为二分其实就是对暴力的搜索过程做优化暴力的check逻辑和二分里的check逻辑是一模一样的。暴力写法大概是这样的伪代码for (int x 1; x MAX; x) { bool ok true; for (int i 0; i n; i) { if (a[i] (long long)x * need[i] * D) { ok false; break; } } if (!ok) { cout x - 1 \n; return 0; } }这段代码的逻辑从 1 开始试找到第一个不可行的 x那答案就是 x-1。如果你把 MAX 设成一个足够大的值它能跑出正确答案但跑得极慢。暴力循环里的内层检查本质就是“判断给定 x 是否可行”。这一段代码原封不动地搬到二分里就是 check 函数。二分优化的不是检查本身而是“下一个该检查谁”的选择策略。暴力检查的顺序是 1、2、3、4……一直往后二分是直接跳到搜索区间的中点一次检查干掉一半。2.2 二分答案的 check 函数怎么写check 函数是二分答案的心脏。在制药这道题里check 函数接受一个日产量 mid返回它是否可行。我在草稿纸上写的 check 大概是这样的bool check(long long x) { // 每天生产 x 份连续 D 天第 i 种药材总消耗是 x * need[i] * D // 只要有一种药材不够就返回 false for (int i 0; i n; i) { if (a[i] (long double)x * need[i] * D) { return false; } } return true; }这里有一个很重要的工程细节x、need[i]、D 三个数相乘很容易超出 int 范围。假设 x 1e9need[i] 1e9D 1e9乘积是 1e27int 早爆了long long 最大也就 9e18一样会爆。所以我在临时草稿里用 long double 做比较先保住精度后面完整代码里我会改用更稳的办法。check 函数的本质就是判断所有原料是否都能支撑到 D 天。它的时间复杂度是 O(n)每次判定都要遍历所有药材。这个 O(n) 是少不了的因为任何一种药材断料都会导致整个方案不可行。2.3 二分答案的搜索范围怎么划定check 写好了接下来要确定二分在哪个范围里找答案。这道题的答案最大日产量理论下界是 0因为如果某种药材库存为 0一份都生产不了。上界怎么定最稳妥的做法是直接从题目给定的数据上限推。比如你知道每种药材库存最大是 1e9need[i] 最小是 1D 最小是 1那答案理论上最大也就是 1e9。但为了防止自己把上界算小了我一般习惯把二分上界设成一个“绝对不可能可行”的大值比如 1e18然后在循环里通过 check 收敛比手算一个精确上界要省心得多。还有人会问为什么不能把上界设成无穷大二分要求上界是一个明确的值不能是无穷。而且如果你设的值太大比如 1e18二分的次数也就多十几次而已完全不影响性能。这里的权衡是上界宁可设大绝对不要设小设小了答案会被卡住设大了不会。二分模板我常用的是找最大可行值这一套long long l 0, r 1e18; // r 一定不可行或可行? 见下面说明 while (l r) { long long mid (l r 1) 1; if (check(mid)) l mid; else r mid - 1; } cout l \n;这里的 r 初始值需要保证一件事要么它可行要么它不可行都行关键是 l 必须从一个可行值开始。因为我们找的是“最大可行值”所以 l 从 0 开始最安全因为日产量为 0 一定可行即使一种药材都没有0 份也做出来了严格说就是不做任何生产也不存在断料的问题。r 从头到尾只是一个“搜索上界”不需要保证它可行只要它不小于真实答案即可。这里的 mid 计算用的是 (l r 1) 1为什么要加 1这是为了避免死循环。当 l r - 1 时如果 (l r) 1 会等于 lcheck(l) 如果可行更新 l mid ll 不变循环就永远跳不出去。加上 1 之后mid 会取到 r保证区间会不断缩短。3. 完整AC代码与关键细节3.1 完整代码实现直接上我调好的版本用 __int128 避免中间乘法溢出这在 XTUOJ 这类数据范围比较奔放的OJ上非常实用#include bits/stdc.h using namespace std; using ll long long; ll n, D; vectorll a, need; bool check(ll x) { if (x 0) return true; for (int i 0; i n; i) { // 用 __int128 保证 x * need[i] * D 不会溢出 __int128 use (__int128)x * need[i] * D; if ((__int128)a[i] use) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n D; a.resize(n); need.resize(n); for (int i 0; i n; i) cin a[i]; for (int i 0; i n; i) cin need[i]; ll l 0, r 1e18; // 也可以把 r 设成所有 a[i] / need[i] 的最小值 1但 1e18 更省事 while (l r) { ll mid (l r 1) 1; if (check(mid)) l mid; else r mid - 1; } cout l \n; return 0; }这段代码在 OJ 上跑是稳过的。需要注意我的输入顺序是先读 n 和 D然后读库存数组然后读单份消耗数组。你实际做题时如果输入顺序不一样记得调整这种低级错误会导致整个逻辑全部错位而且是那种看着代码完全没问题、样例一半过一半挂的诡异状态。3.2 check 函数逐行拆解我见过很多人在 check 函数里翻车这里仔细讲一下。if (x 0) return true;这一行是我后来加上的。理论上如果把 l 从 0 开始check(0) 一定会被调用到此时 x * need[i] * D 0a[i] 0 恒成立所以即使不写这行结果也是 true。但写上这行有几个好处一是显式表达“不生产一定可行”的边界语义二是在一些诡异的变体题里x 为 0 可能导致除以某个数为零提前返回能避坑。__int128 use (__int128)x * need[i] * D;这是我反复强调的防溢出写法。你可能觉得没必要觉得题目数据范围不会那么大。但 OJ 题目的数据范围往往不会明明白白告诉你它有多毒我见过太多 int 溢出导致的 WA调试半天最后发现是乘爆了。用 __int128 多写几个字符能省掉一整晚的调试时间这笔账怎么算都划算。if ((__int128)a[i] use) return false;这里是“短板效应”的体现只要有一种药材不够整个方案就不可行。注意__int128和ll比较时编译器一般会做隐式提升但为了更明确、更保险我还是把它也转成__int128。这种细节不会让你的代码变慢但会减少很多莫名其妙的编译器警告。3.3 两种二分边界模板到底该怎么选网上二分模板五花八门核心就两种一种是找“最后一个可行值”另一种是找“第一个不可行值”。制药这道题要的是最大日产量所以本质是找最后一个可行的 X。找“最后一个可行值”的模板就是我上面写的while (l r) { mid (l r 1) / 2; if (check(mid)) l mid; else r mid - 1; }另一种是找“第一个不可行值”的写法while (l r) { mid (l r) / 2; if (!check(mid)) r mid; else l mid 1; }两种写法结果上能对但容易混。我的建议是不要总换模板就固定记死一种并且能说清楚它的不变式。我个人固定记“l 永远是一个可行值r 永远是一个不可行值”这种方式然后把答案锁定在 l 上。这里有一个关键认知r 初始值如果是一个“不可行值”你在执行r mid - 1时需要小心。比如我上面用 r 1e18如果 1e18 其实是可行的理论上几乎不可能因为库存不可能那么大那r mid - 1可能会把可行区间砍掉。保险的做法是让 r 从一个“绝对不可能达到”的大值开始或者把 r 的可行性问题显式处理。大多数题解为了方便都会让 l 0可行、r INF极大但不可行或至少不小于答案配合(l r 1) 1的模板基本万无一失。如果你实在担心也可以采用一个更保守的二分写法在二分结束后对 r 做一次 check判断一下是 l 还是 r。但说实话只要模板固定检查清楚初始值语义这些额外操作都不需要。4. 实战坑点与排查清单4.1 WA边界和溢出的排查顺序这道题最容易WA的点我按出现频率排个序。第一是溢出。用 int 存 x、need[i]、D乘积一上来就爆样例可能小正好能过但提交上去就WA。排查方法很简单把所有的中间量都改成 long long必要时用 __int128这是性价比最高的改动。第二是输入顺序读错。有时候题面先给库存再给消耗有时候先给消耗再给库存还有时候 n 后面跟的不是 D 而是别的变量。我建议每次敲代码前先在草稿纸上把“我假设的输入格式”写清楚再对着题面逐行核对。不要觉得这是小事我在 OJ 上帮人 Debug 时发现相当一部分WA就是输入读串了。第三是最小边界问题。比如 n 1need[0] 0 怎么办need 是0意味着这种药材不受消耗影响你的 check 里把它当正常药材比较也不会出错但如果你写了一个除法式子比如a[i] / (x * need[i])那 need 0 时直接除零崩溃。所以 check 里尽量只写乘法不写除法这是一个很好的习惯。4.2 TLE不是二分本身慢而是写崩了有些同学二分写对了但提交显示TLE就开始怀疑“二分难道不是log级吗怎么可能超时”其实问题通常不出在二分而是出在二分外面的壳。最常见的原因是输入输出。数据量一大cin/cout 不关同步直接原地爆炸。在 main 里加上ios::sync_with_stdio(false); cin.tie(0);这一行可以解决绝大多数因为 IO 导致的 TLE。有人还会问为什么不用 printf/scanf那当然也可以但既然用 C 流就一定要关同步这是基本功。另一个TLE原因是你把 check 函数写成了 O(n log n) 甚至更高。比如检查某种药材的时候又排序、又二分查找这完全没必要。这道题的 check 必须是严格的 O(n)一重循环走完任何多余的排序、STL操作都会把二分好不容易省下来的复杂度又吃回去。还有一种隐蔽的 TLE 是死循环——如果你把二分模板写成while (l r)l mid那种当l mid等于原值的时候l 永远不变程序就卡死在循环里。表面上看是TLE实际是死循环。遇到TLE别急着怪数据范围先在本地跑一个极端数据试试看看能不能在一秒内跑完。4.3 由“NTC查表二分不准”引出的单调性思考我在搜这道题相关资料的时候看到有个热搜词叫“ntc查表 二分法不准”当时就乐了。虽然这是嵌入式领域的一个话题但它背后涉及的二分法原理恰好能解释很多人在 OJ 上“二分写对了却总觉得不准”的困惑。NTC 热敏电阻的温度-ADC 查表很多教程会让你用二分法在表里找目标温度但实际操作中经常出现“查出来的温度差几度”的情况。原因也很简单二分法要求被搜索的序列必须是严格有序的而 NTC 的 ADC 采样表在高温段、低温段往往存在非线性畸变甚至有些表因为采样噪声根本不是严格单调的。你二分得再准也是在一张本身有毛刺的表上找值结果自然会有误差。这和“制药”这道题有什么关系关系大了。二分答案的 check 函数本质上就是一张“可行性表”它的横轴是日产量 X纵轴是可行/不可行。如果这个 check 函数写得不对导致可行性不单调——比如某些 X 不可行但更大的 X 反而可行——那么你的二分就会在一个错误的区间里乱跳最后得出一个看似正常但实际错误的答案。所以当 OJ 告诉你WA的时候第一个该怀疑的不是二分模板而是你的 check 函数是否真的满足单调性。我之前碰到过一个同学他的 check 里漏了一种药材结果答案偏大还有一个同学把库存数组读成了单份消耗数组整个 check 的单调性都乱了但他死磕二分边界调了一个下午。这些都是“二分本身没问题问题出在二分外面”的真实案例。5. 从这道“制药”题沉淀下来的通用二分套路5.1 二分查找 vs 二分答案两个完全不同的问题很多初学者分不清二分查找和二分答案看到题目说“用二分法”就套标准二分查找模板结果一做一个错。这两个东西长得像但本质完全不同。二分查找面对的是一个已经有序的数组你要在里面找一个目标值主角是“位置”你要找的是这个值在哪个下标。而二分答案面对的是一个值域区间你不知道答案是多少但你能判断任意一个值“行不行”主角是“可行性”你要在可行与不可行的分界线上找到那个最优值。维度二分查找二分答案搜索对象有序数组中的某个下标答案所在的数值区间核心判断a[mid] target?check(mid) 是否可行单调性来源数组有序问题的天然单调性质典型场景找数字、找插入位置最大化最小值、最小化最大值易错点边界下标处理check函数写错、溢出制药这道题是妥妥的二分答案你要在“日产量”这个数值区间里找最大可行值。所以别再想着对某个数组做二分查找了你要二分的是答案本身。5.2 识别二分信号的三个条件不是所有最优解问题都能用二分能用二分的题一般同时满足三个信号。第一个信号题目要求最大化或最小化某个值。比如“最大日产量”“最少需要多少天”“最短可行时间”。制药题要求“最大日产量”信号非常明显。第二个信号给定一个值判断它是否可行比直接算出最优值容易得多。制药题里给定任意 X我只需要遍历每种药材检查够不够用但要我直接写出最大 X 的公式反而没那么直观。能判断可行性是二分答案操作的前提。第三个信号可行性随答案单调变化。这一点前面已经反复强调过产量越高越不可行产量越低越可行这就是单调。有些题表面看不出来单调性比如涉及取模运算、涉及除法取整但经过数学转换后往往也能抽出一个单调关系来。这三个条件缺一不可。我在做别的OJ题时还会刻意提醒自己如果一道题可以贪心直接算出答案就别硬套二分只有当你发现“直接算很难但判断可行性很容易”的时候二分才是最优解。5.3 工程化习惯防溢出、调试技巧和模板固化最后聊一些能提高实战效率的习惯这些都是我在这个题和类似题上反复踩坑总结出来的。第一能用 long long 就不要用 int。OJ 的数据范围从来不会嫌你变量类型太大但一定会让你为 int 溢出买单。涉及乘法的时候直接改成 __int128一劳永逸。第二写 check 函数时尽量把所有中间变量都定义成 long long 或 __int128不要混用。混用短期看不出问题一旦数据到达上界隐式类型转换会把你坑到怀疑人生。第三二分模板要固化。我个人推荐把下面这个模板背下来遇到“最大化一个值”的题直接套用long long l 0, r 1e18; // 或根据题目数据范围调整 while (l r) { mid (l r 1) 1; if (check(mid)) l mid; else r mid - 1; }这里我再说一次为什么用(l r 1) 1而不是(l r) 1当 l 和 r 只差 1 的时候如果取靠左的中点check(mid) 通过则 l 不变死循环靠右的中点保证 l 一定会增加循环绝对会退出。这是一个很小的细节但能省掉你大量调试时间。第四调试时可以先造几组极端数据。比如 n 1、库存只有 1、need 为 1、D 为 1答案应该是 1比如某种药材库存为 0答案应该是 0比如库存和 need 都极大检查会不会溢出。这些边界数据在本地过了基本就稳了一半。我在做这道题时其实还犯过一个更蠢的错把 D 直接当成天数循环写了一个按天模拟的版本结果当然是TLE。后来我才意识到这道题根本不需要模拟每天的生产过程直接把“连续 D 天”换算成“总消耗量”就是一个乘法一笔账全算清楚了。所以遇到这种带天数、带产量的题先想清楚它是在考模拟还是要考数学建模再决定写什么代码。如果你把这道题吃透了后面再遇到最小化最大值、最大化最小值类型的题比如跳石头、切木棍、运货问题都会觉得顺畅很多。本质上它们都是同一个骨架只是 check 函数的业务逻辑不同而已。我在实际应用里也发现很多工程问题里“猜一个参数、验证可行性、再调参数”的思路就是二分答案的现实翻版。所以别小看OJ上的这一道小题它训练的是一种非常通用的优化思维。