wqs二分

wqs二分是用于求解这样一类问题的：

有若干个物品，要求选出m个物品，且选的时候有某种限制，求出最佳方案。

设$g(i)$表示选$i$个物品的最佳方案
wqs二分适用的条件是，将所有的$(i,g(i))$画在二维平面上，这些点是上凸或下凸的。
这种题的特点是如果不限制选物品的个数，可以很容易求出来。
由于$(i,g(i))$构成一个凸壳，我们考虑二分一个斜率$k$，因为凸壳上斜率是单调的，通过斜率的变化可以找到决策点。
当二分出一个$k$的时候，要找到其对应的最优决策点，我们发现与凸壳相切且斜率为$k$的直线的纵截距是$f(x)=g(x)-kx$，$x$就是我们要求的最优决策点。
考察一下$f(x)$的意义，选出$x$个物品后最优价值为$f(x)=g(x)-kx$，其实就是原本的物品全都减掉$k$的价值后求出的最大价值，那么根据前面说的，这里就没有个数限制，非常好求。
求出最大价值的同时可以求出$x$，这就是我们二分的依据了，根据$x$和要求的$m$之间的大小关系以及凸壳的斜率变化方向，改变二分的边界。