洛谷P3743小鸟的设备：浮点二分答案与check函数全解析

洛谷 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; }用几个边界样例实测一下。样例一n1p1设备耗电 2、初始电量 1。1 1 2 1单个设备每秒净耗电 2-11初始 1最多撑 1 秒。程序输出 1.00000000。样例二n2p5两台设备都是每秒耗电 1、初始电量 0。2 5 1 0 1 0sumA2p5 2输出 -1。这里如果只写p sumA就会漏掉 p sumA 的边界所以判断必须写成p sumA。样例三n2p1两台设备都是每秒耗电 1、初始电量 1。2 1 1 1 1 1sumA2p1有限运行。sumB2sumA-p1所以上界 r3。check 过程会收敛到 2.00000000。直观理解两台设备各自每秒耗 1充电宝每秒只能供 1相当于系统总电量从 2 开始以每秒 1 的速度衰减极限是 2 秒。这个样例正好说明了极限答案的含义实际上没有任何调度能让设备在整整 2 秒内都不归零但可以无限逼近 2 秒所以输出 2.00000000 是正确的。7. 举一反三怎么认出下一道二分答案题P3743 做完之后我最大的收获不是会了这一道题而是学会了一类题的识别方法。二分答案题往往有这三个特征第一题目让你求的是一个最大可行值或最小可行值而直接求非常难甚至无从下手。第二给定一个候选值 X你能用一个相对简单的函数判断它是否可行这个函数不需要给出具体构造方案。第三可行性和候选值之间存在单调性X 越大或越小会导致可行性单调翻转。只要同时满足这三条就优先考虑二分答案。类似套路在 OI 题里很常见比如木材加工问题给定若干根木头要求切成 k 段长度相等的木段求单段的最大可能长度。它就是二分单段长度 L然后检查所有木头能切出的总段数是否不少于 k。再比如跳石头问题移走若干块石头求最大化最小跳跃距离也是典型的二分答案。它们的共同点都是 check 函数比原问题好写得多。最后补一个我做浮点二分时的个人习惯二分次数固定写 100不要用 while(r-leps)判断 -1 或特殊解要放在二分之前check 里能用提前剪枝就提前剪。这三个习惯让我后来再做任何浮点二分题都没再翻过车。如果你也被这道题卡过希望这篇能把最后那层窗户纸捅破。