洛谷 P3743 小鸟的设备，是我卡了整整一个晚上的题。当时我看题面特别短，以为就是个贪心模拟，写了几十行，样例也过了，结果一交全是 WA。后来翻了几篇题解才反应过来：这道题考的是二分答案，而且是浮点二分里最容易出细节的那一类。这篇文章把我从"看不懂别人代码"到"自己能推出来"的整个思考过程写出来，包括题目怎么建模、为什么不能模拟、check 函数里的账本式判定、无限怎么判断、二分上界怎么取、精度怎么处理，最后附上完整可交的 C++ 代码。适合正在学二分答案、或者被这道题折磨了一晚上的同学参考。
1. 题面先翻成大白话：n 台设备、每秒耗电和那个充电宝
先别急着看题解，把原题翻译成我们熟悉的语言。你有 n 个设备，第 i 个设备每秒消耗 a[i] 点电量，初始有 b[i] 点电量。手里有一个充电宝，输出功率是 p，意思是每过 1 秒，你只能挑一个设备，给它注入 p 点电量。注意是"每秒只能给一台设备充电"，不能同时给多个设备分电。设备电量降到 0 或负数就算停止工作，你要让所有设备一起正常工作，问最多能撑多少秒。如果能无限撑下去，就输出 -1。
这个问题其实是在问：所有设备电量都保持非负的最大时间 T 是多少。由于充电可以随时开始随时结束，T 不一定是个整数，这是第一个要建立的认知。比如一台设备每秒耗 2 点电，初始有 1 点电，充电宝每秒能充 1 点电，那它的净消耗速度就是每秒 1 点电，最多撑 1 秒。这个答案可以是 1、可以是 1.5、也可以是 1.732，本质上是连续的。
还有一点容易被忽略：题目里"电量可以到 0"，意思是到 0 的那一刻就不再属于正常运行了，所以实际能撑的时间通常是一个上确界，而不是某个能精确达到的值。后面讲精度和 check 的时候会再提到这个性质，它不影响二分答案的正确性，但会影响你对答案的理解。
输入规模上，n 是十万级别，a[i]、b[i]、p 都不是小数目，答案可能会非常大，所以要提前想好用多少位浮点数来存，这就是后话。现在先把模型的数学形式列出来：
- 总耗电速率：sumA = sum(a[i])
- 总初始电量：sumB = sum(b[i])
- 充电宝 t 秒内最多能提供的电量：p * t
只要把这三个量放在心里，后面所有的推导都围绕它们展开。
2. 为什么这题不能用模拟硬解：连续时间里的调度噩梦
我第一次做这题时，脑子里冒出的方案很简单：每秒开始前，看哪台设备电量最低，充电宝就给谁充。这个贪心直觉非常强，电量最低的设备最危险，帮它回血总没错。但提交之后 WA 得很惨，问题在于"每秒"这个粒度根本不够。
试想，一个设备每秒耗电 100，初始电量只有 1，它 0.01 秒就没了。你以一个固定时间步长去模拟，比如 dt = 0.5 秒，那它会直接跳过"设备已经没电"的瞬间，模拟结果完全失真。要把时间步长缩小到能捕捉所有设备耗尽的时刻，步长要无限小，这显然不现实。
有人会想到事件模拟：记录每台设备电量耗尽的时间点，只在这些时间点做决策。但这里有个隐藏的坑——充电切换并不一定发生在设备耗尽的那一瞬间。最优方案可能在电量还剩 30% 的时候就开始切换充电对象，因为要提前给另一台设备续命。于是你能列出的事件类型无限多，而一旦引入连续切换时刻，复杂度就彻底失控。
再退一步，就算真的去贪心"每台设备电量最低先充"，也需要严格证明这个决策在连续时间下是最优的。说实话，我到现在也没见过对这个贪心策略的系统性证明，因为它明显会失效：假设一台设备耗电极高，充电宝功率小于它的消耗速度，充电时只是让它掉电变慢；此时把所有充电时间都给它，其他设备就会裸奔耗尽；如果分给其他设备，这台高耗电设备又很快归零。这个权衡本身就是个连续优化问题，贪心根本兜不住。
所以模拟这条路走不通，本质原因是：我们需要精确求一个极值，而极值由无数个可变的切换时间点共同决定。与其在无限维的调度空间里挣扎，不如换一个完全不同的思路——不去求"具体能撑多久"，而是去判断"给定一个时间 T，能不能撑过 T"。这个思路就是二分答案。
3. 关键转折：把"求最长时间"改成"二分猜时间再验证"
二分答案的核心在于找到一个问题从"难"变"易"的转折点。对于"求最长时间"这个原始问题，确实难办；但"判断某段时间内设备们能不能撑住"这个问题，反而可以用一个 O(n) 的账本算法解决。于是我们可以这样操作：先猜一个时间 x，然后验证在 x 秒内所有设备都能不归零。如果验证通过，说明实际答案不小于 x，我们就把下界往上提；如果验证失败，说明答案小于 x，把上界往下压。重复几十次，上界和下界就会逼近真实答案。
为什么这个验证是单调的？如果所有设备能撑过 3 秒，那它们一定能撑过 2 秒、1 秒，因为前 2 秒只是 3 秒的一个前缀，既然整个 3 秒都没归零，前 2 秒当然也没归零。反过来，如果 3 秒撑不过，那 2 秒倒是有可能撑过，这就构成了典型的二分搜索条件：存在一个分界点，小于它的都可行，大于它的都不可行。我们二分的就是这个分界点。
伪代码很直观：
l = 0 r = 某个足够大的上界 重复固定次数（比如 100 次）： mid = (l + r) / 2 if check(mid) 可行： l = mid else： r = mid 输出 l这里有个从做题的人角度必须强调的点：二分答案的难点从来不是二分本身，而是 check 函数。如果 check 写得不好，要么把不可行的时间判成可行，要么反之。接下来这一节就是本题的灵魂——check 到底在算什么。
4. check(x) 的账本算法：差额电量与总供电量
假设现在验证时间 x 是否可行。对单台设备 i，它在 x 秒内一共会消耗 a[i] * x 点电量，而它手里只有 b[i] 点初始电量。如果 b[i] 已经足够覆盖消耗，那这台设备根本不用充电；如果不够，缺口的数额就是：
need_i = max(0, a[i] * x - b[i])这个 need_i 的含义是：为了让这台设备撑满 x 秒，它必须从充电宝这里获得的最少电量。把所有设备的 need_i 加起来，就得到了整个系统对充电宝的总需求。而充电宝在 x 秒内最多能输出 p * x 点电量（因为它的功率恒为 p，每秒都必须输出，闲着也算浪费）。于是验证条件只有一行：
sum(max(0, a[i] * x - b[i])) <= p * x连起来说就是：所有设备缺的电量总和，只要充电宝总输出接得住，这 x 秒就可行。
我第一次看到这个式子时有个疑惑：充电宝同一时刻只能给一台设备充电，那是不是还要模拟一下每台设备到底分到了多少充电时间？答案是不用。这里的定量分析是"总账本"：不考虑充电顺序、只考虑总量，只要总供电量不低于总缺口，就总能通过足够细的时间切片，把电按需分配给各设备。你把 x 秒切成一亿个小片，每个小片只给某一台设备充电，只要每个设备的累计充电量不低于它的缺口，它就不会提前断电。
这个"总账本"思想是 check 函数最精妙的地方，也是这类题目的通用套路：把复杂的调度可行性，抽象成一个关于总量的不等式。不过要注意，它判断的是"能无限逼近地撑过 x 秒"而不是"严格撑满但不差一毫秒"——就像我开头说的，连续时间模型下答案经常是上确界，二分出来的结果会有极小误差，但不影响我们输出精度范围内的答案。
在实现 check 的时候可以加一个小优化：不需要把所有缺额都加完了再比较，每算一个设备就判断一次 need 是否已经超过 supply，一旦超过立刻返回 false。因为 supply 是定值，need 只会越加越大，提前终止可以省下不少计算量，尤其是 n 到十万级别的时候。
5. 三个高危细节：-1 判定、二分上界、浮点精度
这道题从 AC 到 WA 的差别，往往就在这三个地方。我分别说透。
5.1 无限运行判定：p >= sumA 时直接输出 -1
什么时候能无限运行？充电宝的总输出功率 p 至少要不小于所有设备的耗电速率之和 sumA。也就是说，系统的总能量账本始终是正的或持平的：每过 1 秒，设备总共烧掉 sumA 度电，充电宝理论最多供出 p 度电。只要 p > sumA，长期来看充电宝还能给系统"攒电"，任何设备都不会真正耗干；当 p == sumA 时，能量刚好精确对消，也属于可无限运行的情形，所以判断条件要写成 p >= sumA。
注意这个判断必须在二分之前完成，否则你会进入一个死循环：sumA == p 时，分母 sumA - p 为 0，上界根本算不出来。而且如果不做这个判断直接二分，答案会无限增大，二分永远收敛不了。
5.2 二分上界：用 sumB / (sumA - p) 更安全
二分最朴素的做法是把上界设成 1e18 之类的大数，反正二分 100 次也能收敛。但这样做有两个隐患：一是大数乘小数容易出现浮点精度损失，二是直觉上不够精确，不好向别人解释。
更靠谱的上界来自能量守恒推导。如果系统只能在有限时间内运行，那么整个系统的总电量满足一个约束：初始电量 sumB 加上充电宝在 t 秒内提供的电量 p * t，必须覆盖所有设备消耗的 sumA * t。写成不等式：
sumB + p * t >= sumA * t移项得到：
t <= sumB / (sumA - p)当且仅当 sumA > p 时，这个分母才是正数，对应有限运行的情形。把这个值作为初始上界 r，再额外加一点余量（比如+ 1），就保证真实答案一定落在 [l, r] 区间内。用这个上界，一方面数值不会大到离谱，另一方面二分效率也不受影响。
5.3 浮点精度：用 long double，固定二分 100 次
浮点数二分最怕两件事：精度不足和死循环。如果你写while (r - l > eps)，当答案非常大时，eps 稍微开小一点，可能永远退不出循环；开大了，精度又不够。我实测下来最省心的方案是：二分固定跑 100 次。100 次之后，无论初始区间多大，区间长度都会被压缩到原来的 2 的 100 次方分之一，远远超过输出要求的精度。
数据类型方面，用 long double 而不是 double。题目虽然没有给出极端的数值范围，但 a[i] * x 在二分过程中可能达到很大的数，double 大约只有 15 位有效数字，累加误差容易被放大。用 long double 可以明显减少这类误差。
这几个细节的检查顺序建议是：先判 -1，再算上界，再二分，每一步都分开想清楚。下面给出完整代码。
6. 完整 C++ 实现与边界样例实测
直接贴代码，关键位置都有注释：
#include <bits/stdc++.h> using namespace std; using ld = long double; const int MAXN = 100005; int n; ld p; ld a[MAXN], b[MAXN]; bool check(ld x) { ld need = 0.0; ld supply = p * x; for (int i = 0; i < n; ++i) { ld consume = a[i] * x; if (consume > b[i]) { need += consume - b[i]; } // 提前剪枝：缺口已经超出充电宝能力，直接失败 if (need > supply) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> p; ld sumA = 0.0, sumB = 0.0; for (int i = 0; i < n; ++i) { cin >> a[i] >> b[i]; sumA += a[i]; sumB += b[i]; } if (p >= sumA) { cout << "-1\n"; return 0; } ld l = 0.0; ld r = sumB / (sumA - p) + 1.0; // 推导见正文 5.2 // 固定迭代 100 次，避免 eps 精度问题 for (int iter = 0; iter < 100; ++iter) { ld mid = (l + r) / 2.0; if (check(mid)) { l = mid; } else { r = mid; } } cout << fixed << setprecision(8) << l << "\n"; return 0; }用几个边界样例实测一下。
样例一：n=1，p=1，设备耗电 2、初始电量 1。
1 1 2 1单个设备每秒净耗电 2-1=1，初始 1，最多撑 1 秒。程序输出 1.00000000。
样例二：n=2，p=5，两台设备都是每秒耗电 1、初始电量 0。
2 5 1 0 1 0sumA=2，p=5 >= 2，输出 -1。这里如果只写p > sumA就会漏掉 p == sumA 的边界，所以判断必须写成p >= sumA。
样例三：n=2，p=1，两台设备都是每秒耗电 1、初始电量 1。
2 1 1 1 1 1sumA=2，p=1，有限运行。sumB=2，sumA-p=1，所以上界 r=3。check 过程会收敛到 2.00000000。直观理解：两台设备各自每秒耗 1，充电宝每秒只能供 1，相当于系统总电量从 2 开始以每秒 1 的速度衰减，极限是 2 秒。这个样例正好说明了"极限答案"的含义：实际上没有任何调度能让设备在整整 2 秒内都不归零，但可以无限逼近 2 秒，所以输出 2.00000000 是正确的。
7. 举一反三：怎么认出下一道二分答案题
P3743 做完之后，我最大的收获不是会了这一道题，而是学会了一类题的识别方法。二分答案题往往有这三个特征：
第一，题目让你求的是一个"最大可行值"或"最小可行值"，而直接求非常难，甚至无从下手。第二，给定一个候选值 X，你能用一个相对简单的函数判断它是否可行，这个函数不需要给出具体构造方案。第三，可行性和候选值之间存在单调性，X 越大（或越小）会导致可行性单调翻转。只要同时满足这三条，就优先考虑二分答案。
类似套路在 OI 题里很常见，比如木材加工问题：给定若干根木头，要求切成 k 段长度相等的木段，求单段的最大可能长度。它就是二分单段长度 L，然后检查所有木头能切出的总段数是否不少于 k。再比如跳石头问题：移走若干块石头，求最大化最小跳跃距离，也是典型的二分答案。它们的共同点都是 check 函数比原问题好写得多。
最后补一个我做浮点二分时的个人习惯：二分次数固定写 100，不要用 while(r-l>eps)；判断 -1 或特殊解要放在二分之前；check 里能用提前剪枝就提前剪。这三个习惯让我后来再做任何浮点二分题都没再翻过车。如果你也被这道题卡过，希望这篇能把最后那层窗户纸捅破。
