WQS二分学习笔记

前言

$WQS$二分听起来是个很难的算法，其实学起来也并不是那么难。

---

适用范围

在某些题目中，会对于某个取得越多越优的物品，限定你最多选择$k$个，问你能得到的最优答案。

例如这道题目：【CF739E】Gosha is hunting。

$Link$

【CF739E】Gosha is hunting 的题解 详见博客 【CF739E】Gosha is hunting（WQS二分套WQS二分）

这些题目一般都可以通过枚举选择的物品个数并$O(n)DP$来做到$O(nk)$。

但如果随着选择物品个数的增加，得到贡献的斜率是不递增的，我们就可以用$WQS$二分，来将$O(nk)$的时间复杂度优化为$O(nlogn)$。

---

大致思想

$WQS$二分的核心思想其实非常简单。

既然原来选得越多越优，那么我们可以给选择一个物品增加一个代价$C$（$C$可以拿来二分），由于总贡献增长得越来越慢，所以最后肯定会形成一个单峰函数，然后我们就可以通过 $DP$等方式 来求解出此时的最优答案以及最优答案选择的物品个数，并根据选择的物品个数来更新$C$的值。

这样就变成$O(nlogn)$了。

最后的答案就是$f_n+k\ast C$（注意，不能写成$f_n+mid\ast C$）。

---

后记

关于例题，文中提到的【CF739E】Gosha is hunting一题就是 $WQS$二分 一道比较经典的题目，感兴趣的可以自己去看一看、做一做。

【POJ1160】Post Office其实也是一道$WQS$二分的入门题，也是值得一做的。

$Link$

【POJ1160】Post Office 的题解 请参考博客 【HHHOJ】NOIP模拟赛 捌 解题报告的$T2$