wqs二分详解

学这个算法的时候，深切的体会到，能找到一篇好的文章来学习是多么幸福啊……

这是一个用来解决这样一类问题的算法：

有若干个物品，要求你选出 $m$ 个，选的时候带有限制，要你求出最优的方案。

用的时候有一个大前提，就是，设 $g(i)$ 表示选 $i$ 个物品的最优方案，那么将所有点 $(i,g(i))$ 画出来，他们一定要组成一个凸包（上凸下凸皆可），所有点都在上面的那种，这样就有一个性质：斜率单调递增或递减。

这种题的特点是：如果不限制选的个数，很容易就能求出最优方案。

下面以上凸包（从左到右斜率递减）为例子。

现在，我们的目标就是，求出 $g(m)$ 。

做法是，二分一个斜率 $k$ ，然后找到斜率为k的切这个凸包的直线切于哪一点。

可以发现，随着 $k$ 的减小，这条直线切的点会越来越靠右，就像这样：
wqs二分详解（这图也不算太严谨，因为有些点没画，比如 $(2,g(2))$ 之类……）

于是我们二分 $k$ 直到这条直线切的点的横坐标是 $m$ ，那么这个点的纵坐标 $g(m)$ 就是答案了。

于是问题变成了：当二分出一个 $k$ 时，怎么求被切的点是谁。

很有规律，你康康这个就懂了：
wqs二分详解被切点上的直线，是在最上面的，也就是说，这条直线在 $y$ 轴上的截距最大。

设这个截距为 $f(x)$ ，那么经过点 $(x,g(x))$ 的斜率为 $k$ 的直线在 $y$ 轴上的截距就是 $f(x)=g(x)-kx$ 。

现在问题变成了，找到最大的 $f(x)$ 。

考虑一下 $f(x)$ 的意义，他等于 $g(x)-kx$ ，而 $g(x)$ 等于选 $x$ 个物品时的最优解，那么 $f(x)$ 就相当于选的每个物品的价值都减 $k$ 后的最优解。

由于我们现在要求的是最大的 $f(x)$ ，也就是所有物品的价值都减 $k$ 之后的最优解，根据上面的特点，在没有数量限制的情况下，最优解是很容易求的，于是就做完啦！

最后再讲讲 $l,r$ 的调整，当此时的 $k~(k=\frac {l+r} 2)$ 求出来的最大的 $f(x)$ 的 $x$ 小于 $m$ 时，根据图像，很容易知道我们应该将斜率减小，也就是让 $r=mid$ ，这样才能让切点右移，从而逼近点 $m,g(m)$ 。

大多题目在整数域内二分即可，有些特别的题可能需要将斜率二分到小数级别。

~~可能还会更新的qwq~~