WQS二分这个技巧我最早是在做「恰好选 k 条白边的最小生成树」这类题时撞见的。当时题解里轻描淡写一句给白边加个权值二分这个权值就行了我盯着看了半天也没想明白给边加权值跟控制选几条白边到底有什么关系二分出来的那个数又代表了什么含义后来自己动手推了几遍、又踩了不少坑才算把这块骨头啃下来。这篇笔记就按我自己的理解顺序来写先说清楚 WQS 二分到底在解决什么类型的问题再用几何直觉把加权值就能控制个数这件事讲透然后给出能直接抄的代码模板最后重点聊聊我踩过的那些理解误区。很多坑其实不是代码敲错了而是脑子里的模型本身就偏了代码写得再对方向错了照样过不了。内容适合已经会写基础 DP、会写最小生成树但一看到恰好选 k 个就发怵的朋友也适合想把这个技巧从会用提升到敢用的选手。1. 从一道经典题说起WQS二分到底治什么病1.1 一个让人难受的约束恰好选 k 个先摆场景。很多最优化问题的结构其实很干净单独拿出来做一点都不难难就难在题目往往加了一句恰好选 k 个或者至少分成 k 段。比如在一张无向图里求最小生成树但要求其中恰好有 need 条白边把一个序列分成恰好 m 段让每段代价的平方和最小在 n 个物品里恰好挑 a 个让收益最大。这类问题一旦把恰好 k这一维加进来复杂度立马炸开。原因在于这一维约束把原本可以贪心或者线性 DP 解决的问题硬生生变成了一个二维问题。原本做最小生成树是 O(m log m)现在要给每条边记录已经选了几条白边变成 O(m log m · k) 甚至更高。原本序列分段是 O(n) 或 O(n log n) 的斜率优化 DP现在要背着分了几段这个状态变成 O(n·m)n 和 m 都上万的时候就彻底没法跑了。这就是 WQS 二分要治的病去掉恰好 k 个这个维度让问题退回它最朴素、最好做的形态再用一个额外的参数把 k 这一维补偿回来。它换来的复杂度通常是一个 log比如从 O(n·k) 降到 O(n log C)C 是二分的值域范围。这个思路一旦理通很多看似无从下手的题目就豁然开朗了。1.2 核心魔法把约束塞进目标函数里WQS 二分的核心操作只有一句话给每一个被选中的单位额外加上一个固定的代价或者奖励这个代价记作 c然后去掉恰好选 k 个的约束直接求全局最优。拿白边生成树举例。原问题是求一棵生成树恰好包含 need 条白边使其总边权最小。我们给每条白边额外加权 c每条白边的实际代价变成 w c。然后跑一遍没有白边数量约束的普通最小生成树只不过在跑的过程中记一下选了多少条白边。这里的 c 就是我们用来调节的旋钮c 越大白边越贵算法自然就倾向于少选白边c 越小白边越便宜算法就多选白边。于是整个问题的结构被改造成了这样原来我们没法控制的量——白边的条数——现在被一个单调的旋钮 c 控制了。我们只需要二分这个 c让算法在最优解里恰好选到 need 条白边就达到了目的。约束没有被消除而是从硬约束变成了软约束再通过调节软约束的力度反过来把硬约束逼出来。为什么这样做是对的、合法的因为在这个过程中我们其实是在探索目标函数关于 k 的一个凸结构。这就引出了下一节也是绝大多数人第一次学 WQS 二分时最容易被糊弄过去的地方——凸性。1.3 不是所有题都能用凸性是硬门槛这一点必须先说清楚否则后面全是空中楼阁。WQS 二分成立的唯一前提是设 f(k) 为恰好选 k 个时的最优值那么 f 作为 k 的函数必须是凸的。什么意思以最小化问题为例f(k) 需要满足相邻差分的单调性f(k1) - f(k) 关于 k 单调不减。直观一点说就是边际代价递增——你多选一个单位付出的额外代价不会比之前少。典型的例子在最小生成树里被迫多塞一条白边进去代价只会越来越亏越往后面越难塞所以它天然是下凸的。反过来如果 f(k) 不凸比如先降后升还带拐点或者干脆是波浪形那 WQS 二分就直接失效了你怎么调 c都没法让最优解的 k 落在你想要的位置上。所以判断一道题能不能上 WQS 二分第一步从来不是想怎么写代码而是问自己——这道题的最优值关于 k 是不是凸的。判断方法通常有三条路。第一把 f(k) 用暴力 DP 打表算出来看差分序列是否单调这是最稳妥的验证手段很多题就靠这一步定生死。第二用交换论证exchange argument证明任意两个解之间做一次交换能让选得多的那个解不比选得少的解更差从而推得凸性。第三凭经验识别典型结构——代价函数是凸的比如平方、绝对值、凸函数求和加约束后往往仍是凸的。作为补充我在实战里优先用第一条因为写个 O(n·k) 的暴力比在纸上证半小时快得多。2. 把几何图画出来为什么加个斜率就能控制个数2.1 答案函数 f(k) 到底在说什么要真正理解 WQS 二分最好把 f(k) 画成一张图。横轴是 k也就是选了几个纵轴是 f(k)也就是恰好选 k 个时的最优值。对于最小化问题且凸的场景这条曲线是一条向下凸的曲线像一口锅左边陡、中间平、右边又翘起来。我们想求的是曲线上 k need 那个点的函数值 f(need)。如果直接去算就得背着 k 这一维做 DP复杂度受不了。但这条曲线的凸性给我们提供了一个抄近路的机会凸函数的每一段都可以被一条直线从下方支撑住而这条直线的斜率恰好就对应着我们那个调节旋钮 c。也就是说与其硬算 f(need)不如换一种方式去描写这条凸曲线用它的所有切线支撑线来刻画它。一条斜率确定的支撑线能告诉我们曲线在某一段上的走势而那条线的斜率正是我们加了惩罚 c 之后去掉约束的那个最优解所对应的东西。这就是整个技巧的几何本质——用切线去反推曲线上的点。2.2 惩罚系数 c 与切点位置的关系现在把惩罚 c 引入进来定义一个新函数 g(c)g(c) min over k { f(k) c · k }这里的 c·k 就是我们给每个被选中的单位额外附加的代价。g(c) 的含义是在所有可能的 k 里找出让原代价加上惩罚最小的那个 k记下这个最小的总值。从几何上看g(c) 就是拿一条斜率为 -c 的直线去从下方逼近 f(k) 这条凸曲线让它尽量贴着曲线最终相切或碰到某个点在某个 k* 上。这个 k*就是当前 c 下最优解所选的个数。于是规律很清楚了c 越大-c 越负直线越陡地向下倾斜切点越往左跑也就是最优解选的个数 k* 越小。c 越小甚至取负值直线越平缓甚至上翘切点越往右跑最优解选的个数 k* 越大。这就是加个斜率就能控制个数的全部秘密。c 不是什么玄学参数它就是切线的斜率是一个用来指定我们想站在曲线的哪个位置看问题的坐标。2.3 二分 c 的单调性从哪来既然 c 和 k* 之间是单调对应的——c 增大k* 减小c 减小k* 增大——那我们就有了二分的依据。我们想要 k* 正好等于 need于是可以在 c 的取值范围内二分当前 c 下算出来的个数 cnt 如果比 need 大说明 c 还不够大惩罚还不够狠得把 c 往上调。当前 c 下算出来的 cnt 如果比 need 小说明 c 太大了得把 c 往下调。反复二分直到 cnt 与 need 对得上。找到这个 c 之后最终答案怎么算这里有一处极易出错的细节我放到误区章节里细讲先记住结论f(need) g(c) - c · need。因为 g(c) 里把每个被选单位都多加了 c 的代价我们要还原回恰好 need 个的真实值就得把这 need 份惩罚扣掉。单调性为什么一定成立根子还在凸性上。如果 f 不是凸的切点位置随 c 的变化就可能来回横跳二分立刻失去意义。所以再次强调凸性不是装饰是二分能成立的数学地基。3. 能直接抄的代码模板与逐行拆解3.1 通用框架长什么样WQS 二分的代码骨架非常固定剥掉题目的外壳后就是一个外外二分套内部求解的双层结构。外层二分 c内层解决去掉约束后的原问题并顺便统计个数。我用 C 写一个通用模板// check(c) 返回在给每个选中单位附加代价 c 之后 // 原问题的最优值以及在最优解中选中的个数tie-break 时选更多 pairlong long, int check(long long c); // 目标计算 f(need)即恰好选 need 个时的最优值 long long wqs(int need) { long long lo -1e12, hi 1e12, best 0; while (lo hi) { long long mid lo (hi - lo) / 2; auto [val, cnt] check(mid); if (cnt need) { // c 还能更大 best mid; lo mid 1; } else { // c 太大了 hi mid - 1; } } auto [val, cnt] check(best); return val - (long long)need * best; // 减掉 need 份惩罚 }这一段里藏着三个容易写错的地方逐个说明。第一check在代价相同时要固定一个 tie-break 方向这里选更多否则 cnt 的取值不唯一二分会出现死循环或者答案错误。第二外层用long long存 c 和答案防止溢出c 的量级要留够余量。第三最后那行减的是need * best不是cnt * best原因马上讲。3.2 例题实战最小生成树里恰好选 need 条白边把模板套到具体题目上思路立刻落地。核心改动就是给白边的权值临时加上 mid然后跑克鲁斯卡尔顺便统计选中白边的条数#include bits/stdc.h using namespace std; struct Edge { int u, v, w, c; }; // c1 表示白边c0 表示黑边 int n, m, need, fa[50005]; long long sum; int cnt; vectorEdge e, tmp; int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } bool cmp(const Edge a, const Edge b) { if (a.w ! b.w) return a.w b.w; return a.c b.c; // 权值相同时白边优先选更多白边 } void kruskal(int add) { tmp e; for (auto x : tmp) if (x.c) x.w add; // 白边加惩罚 sort(tmp.begin(), tmp.end(), cmp); for (int i 1; i n; i) fa[i] i; sum 0; cnt 0; int used 0; for (auto x : tmp) { int ru find(x.u), rv find(x.v); if (ru rv) continue; fa[ru] rv; sum x.w; if (x.c) cnt; if (used n - 1) break; } } int main() { scanf(%d%d%d, n, m, need); e.resize(m); for (int i 0; i m; i) scanf(%d%d%d%d, e[i].u, e[i].v, e[i].w, e[i].c); int lo -105, hi 105, ans 0; while (lo hi) { int mid (lo hi) 1; kruskal(mid); if (cnt need) { ans mid; lo mid 1; } else hi mid - 1; } kruskal(ans); printf(%lld\n, sum - 1LL * need * ans); return 0; }几点说明。排序里那条a.c b.c就是 tie-break保证在权值打平时优先吃白边这样 cnt 是同代价下白边数量的最大值与二分判据配合。另外二分区间给足余量这里数据里边权在 0 到 100 之间取正负 105 足够覆盖因为 c 的取值范围本质上是任意一条边到另一条边的差值所能达到的斜率。最后那行sum - need * ans是在还原真实代价把多算的惩罚扣回来。3.3 例题实战DP 场景下的 WQS 二分WQS 二分绝不只是生成树的专利它和斜率优化、决策单调性这些 DP 优化是天然好搭档。拿把序列恰好分成 m 段使每段代价平方和最小这类经典题举例原本需要 O(n·m) 的二维 DP套上 WQS 二分后只需在每段代价里加一个 cdp[i] min over j i { dp[j] cost(j1, i) c }外层二分 c内层用斜率优化或单调队列把这一层 DP 压到 O(n)并同时记录最优解对应的段数。当某一处 DP 时同时存在多个 j 给出相同的最优值就按 tie-break 选段数更多或更少的那个。整个复杂度从 O(n·m) 降到 O(n log C)n 到十万、m 到十万都不虚。这里的关键心得是内层 DP 的转移要能顺便把段数带出来。最干净的做法是在 dp 数组旁再开一个数组记段数或者让 dp 值用一个结构体承载代价 段数两个字段比较时先比代价代价相同再按 tie-break 比段数。这个小设计不改动转移式子本身却能保证 WQS 二分拿到正确的 cnt。3.4 二分上下界和精度怎么定二分上下界的选取经常被忽略但选不好会直接导致 WA 或者 TLE。整数二分时理论上 c 的绝对值不会超过任意两个候选方案的边际代价之差的绝对值上界实际写题时可以直接取一个最大边权或最大单段代价的量级做边界比如边权不超过 100 就取 [-105, 105]。取大一点不影响正确性只多几个 log但取小了可能把正确答案卡在外面。实数二分很多期望类、概率类题目需要则不能靠 tie-break得用精度控制double lo 0, hi 1e9; for (int iter 0; iter 100; iter) { // 定次数比 while 更稳 double mid (lo hi) / 2; auto [val, cnt] check(mid); if (cnt need) lo mid; else hi mid; }固定迭代次数比如 60 到 100 次比用while (hi - lo eps)更稳能避免精度边界上的死循环或抖动。多数情况下 60 次迭代后精度已经远超需要的量级。4. 常见理解误区逐条击破4.1 误区一只要题目带个 k 就能上 WQS 二分这是我见过最多的误区。很多人一看到恰好 k就条件反射地上 WQS 二分结果写着写着发现过不了回头一看——这题的 f(k) 根本不凸。最典型的反例就是带正负权重的背包问题恰好选 k 个物品让总和最大答案关于 k 完全没有凸性可言可能选 2 个赚翻了选 3 个反而亏选 4 个又赚波浪式起伏。这种题无论怎么二分 c都没法让最优解的 k 落在指定位置。**牢记WQS 二分是一把针对凸结构的钥匙不是万能开锁器。**判断凸性优先顺序应该是先打表暴力算 f(k) 看差分差分单调才继续不单调直接换算法比如正经的 O(n·k) DP 或者别的技巧。花五分钟打表比花两小时调一个注定错的代码划算太多。4.2 误区二三点共线时不知道怎么办第二类高频坑是三点共线也就是 f(k) 曲线在某一段上一连好几个 k 落在同一条直线上对应同一个斜率也就是同一个 c。这时候会出问题按这个 c 去 check最优解的个数不唯一可能返回 need-2可能返回 need3全看算法内部的平局怎么断。如果你没设 tie-breakcnt 就变成一个飘忽的值二分可能死循环也可能漏掉正确答案。解决办法就是tie-break在代价完全相同时强制算法偏向某一个方向选更多或选更少。这样 cnt 就变回单调可控二分才稳。具体选哪个方向要和你的二分判据匹配如果你用的是找最大的 c 使 cnt need就 tie-break 选更多反之则选更少。下面给一张对照表二分判据tie-break 方向最终减去的量找最大 c 使 cnt need平局选更多need · c找最小 c 使 cnt need平局选更少need · c两种写法都对但判据方向和 tie-break 方向必须配套混用必错。这是我调试时踩过的最深的坑之一两个方向一错样例能过、大数据全挂非常折磨。4.3 误区三最后答案的减法是 k·c 还是 cnt·c第三类坑藏在最后一行。很多人检查完以后直接拿 check 返回的 cnt 去减写成val - cnt * c这是错的。原因很简单我们要的是恰好 need 个的答案check 返回的 cnt 可能是 tie-break 之后偏大的一个数它并不等于 need。而 g(c) 这个值里已经包含了 cnt 份惩罚我们要还原到 need 份减的必须是 need。所以正确写法永远是val - need * c。判断依据是我们真正想求的是 f(need)而不是check 返回的那个解的值。因为三点共线时 f(need) 和 f(cnt) 落在同一斜率段上g(c) - c·need g(c) - c·cnt恰好相等所以单纯从数值上你可能看不出错误——但在逻辑上减 need 才是对的也更容易在别的题上不出错。4.4 误区四把惩罚方向搞反、二分方向跟着错第四类坑是符号混乱。惩罚我们是加上去让选一个更贵还是减去让选一个更便宜这决定了 c 增大时 cnt 是变小还是变大进而决定二分往哪边走。这两种符号约定都有人用但必须前后一致。我的建议是永远采用给被选中的单位加正惩罚 c这一种约定然后把c 越大、选得越少当成本能。这样思维负担最小二分判据也就固定下来cnt 比 need 大就增大 ccnt 比 need 小就减小 c。千万不要在一道题里一会儿加一会儿减符号一乱二分方向必然跟着乱最后连自己错在哪都看不出来。4.5 误区五实数二分的精度陷阱最后一类坑出现在实数二分。有人直接把整数二分的模板改成浮点用while (hi - lo 1e-12)收尾结果要么迭代次数不够精度不达标要么边界抖动导致死循环。实数场景的正确姿势是固定迭代次数60 到 100 次不依赖 eps 判断。同时要注意实数场景下检出的 cnt 本身就是近似的tie-break 不再可靠最终答案可能需要用二分出的 c 重新跑一遍取精确值再修正。还有一个隐藏得比较深的细节当问题的最优斜率本身就是分数时整数二分根本表示不了必须用实数二分。判断方法还是那招——打表看相邻差分的比值如果出现非整数就老实上实数二分。这类题在做期望类问题时特别常见比如两种捉球策略叠加的期望最大化提前意识到这一点能省下大量调试时间。5. 实战排查清单与踩坑实录5.1 凸性怎么验证先暴力后优化我个人的固定流程是拿到题先写一个 O(n·k) 的暴力 DP或者暴力枚举把 f(0) 到 f(n) 全部算出来打印然后手动看差分序列d[i] f[i1] - f[i]是否单调。如果单调放心上 WQS 二分如果不单调立刻放弃改路线绝不头铁。这个习惯帮我省了无数次无效调试。因为很多时候题目的凸性是看起来像但其实不是光靠直觉容易翻车。打表验证只要几分钟而且一旦确认凸性后面写起来心里就有底了。附带一个好处暴力算出的 f(need) 还能当对拍的标准答案跟 WQS 二分的结果一比正确性立现。5.2 tie-break 策略对照与选择tie-break 到底选更多还是更少不是随便定的要和二分逻辑严格配套。我用下面这张速查表来提醒自己场景建议 tie-break理由找最大 c 使 cnt need平局选更多保证 cnt 是取到上界二分判据成立找最小 c 使 cnt need平局选更少保证 cnt 是取到下界二分判据成立实数二分不需要 tie-break用固定迭代次数最后重算修正换句更口语的话说**你的二分要往哪个方向逼tie-break 就得顺着哪个方向躺。**方向一致三点共线就不再是问题方向相反再简单的题也会莫名其妙挂掉。5.3 常见报错与现象速查表调试时症状往往比错因更早出现我整理了一份看现象猜病根的表现象可能原因排查方向样例过、大数据 WAtie-break 方向与二分判据不配套检查排序/比较函数的第二关键字二分层数跑满但答案偏大/偏小最后减的是 cnt·c 而非 need·c检查收尾表达式程序卡死不退出整数二分区间没收敛或实数二分用了 eps整数检查边界实数改成固定迭代次数答案量级明显不对差一个数量级中间值溢出用了 int把 c、sum、答案全改 long long部分点对部分点错凸性只在大范围成立小处有平局打表看差分补上 tie-break二分越界取到区间端点上下界给得太窄把 c 的范围放宽到边权/代价差值的上界这张表基本覆盖了我遇到过的九成以上 WQS 二分事故。遇到问题时先对照现象定位能省下大量盲猜的时间。6. 我个人在实战里的几点体会写了这么多题之后我最大的体会是WQS 二分的难点从来不在于代码有多复杂——它的代码骨架短得可怜翻来覆去就是二分套求解。真正的门槛在于你是不是真的理解了它背后那个凸结构以及你能不能把 tie-break、符号、收尾这三件事配成一套自洽的逻辑。这三件事任何一处不配套代码就会在某个你看不见的角落悄悄出错。如果要用一句话总结我踩坑后最想告诉别人的**先把 f(k) 打表画出来确认它是凸的再动手写二分。**这一步偷懒后面全是坑这一步做扎实你会发现 WQS 二分其实是个非常讲道理的技巧它不试图去硬解那个 k 约束而是绕个弯用一条切线的斜率把想要的点从凸包上捞出来优雅又干净。等你哪天能看着一道题意就知道该往哪个方向二分、tie-break 该往哪边躺这个技巧就算是真正长在你身上了。