企业官网建设流程全解析

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 份药品已经断料了，那 X+1 份就更不可能够。

用生活化的话说：产量越高，药材消耗越快，可行性只会越来越差；产量越低，日子越好过，可行性只会越来越好。所以“可行性”这个属性随着 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 = 1e9，need[i] = 1e9，D = 1e9，乘积是 1e27，int 早爆了，long long 最大也就 9e18，一样会爆。所以我在临时草稿里用 long double 做比较先保住精度，后面完整代码里我会改用更稳的办法。

check 函数的本质就是判断所有原料是否都能支撑到 D 天。它的时间复杂度是 O(n)，每次判定都要遍历所有药材。这个 O(n) 是少不了的，因为任何一种药材断料都会导致整个方案不可行。

2.3 二分答案的搜索范围怎么划定

check 写好了，接下来要确定二分在哪个范围里找答案。

这道题的答案（最大日产量）理论下界是 0，因为如果某种药材库存为 0，一份都生产不了。上界怎么定？最稳妥的做法是：直接从题目给定的数据上限推。比如你知道每种药材库存最大是 1e9，need[i] 最小是 1，D 最小是 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 会等于 l，check(l) 如果可行，更新 l = mid = l，l 不变，循环就永远跳不出去。加上 1 之后，mid 会取到 r，保证区间会不断缩短。

3. 完整AC代码与关键细节

3.1 完整代码实现

直接上我调好的版本，用 __int128 避免中间乘法溢出，这在 XTUOJ 这类数据范围比较奔放的OJ上非常实用：

#include <bits/stdc++.h> using namespace std; using ll = long long; ll n, D; vector<ll> 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 = 0，a[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 = 1，need[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 二分答案：两个完全不同的问题

很多初学者分不清二分查找和二分答案，看到题目说“用二分法”就套标准二分查找模板，结果一做一个错。这两个东西长得像，但本质完全不同。

二分查找面对的是一个已经有序的数组，你要在里面找一个目标值；主角是“位置”，你要找的是这个值在哪个下标。而二分答案面对的是一个值域区间，你不知道答案是多少，但你能判断任意一个值“行不行”；主角是“可行性”，你要在可行与不可行的分界线上找到那个最优值。

制药这道题是妥妥的二分答案：你要在“日产量”这个数值区间里找最大可行值。所以别再想着对某个数组做二分查找了，你要二分的是答案本身。

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上的这一道小题，它训练的是一种非常通用的优化思维。