简介
我们考虑这样一个问题，有 $n$ 个物品，要求选恰好 $m$ 个最大价值
我们令 $f_i$ 表示恰好选 $i$ 个物品的最大价值，然后将 $(i,f_i)$ 画到直角坐标系上
不妨假设从原点到这些点的斜率递增，即想成一个凸壳
我们考虑拿斜率为 $k$ 的直线去切这个凸包（保证切点是凸包上的顶点，注意我们只考虑截距最大的那条直线所切的点，称为这个点对应斜率为 $k$ 的直线
注意到凸包上的每个顶点都对应斜率在某个区间的一些直线且这些区间不相交并依次递增
我们考虑截距 $b=y-kx$,注意到 $y=f_x$，我们考虑将每个物品的价值都减掉 $k$，那么 $y-kx$ 就等于 $f_x$
注意到 $b$ 最大，也就是说 $f_x$ 最大，即我们将这个问题的限制恰好 $m$ 给去掉之后求出来最大值就是截距 $b$，且我们知道这个斜率 $k$ 对应的是 $x$
也就是说我们可以二分 $k$，从而找到对应 $m$ 的斜率 $k$，然后求出 $f_m$
细节
然而带权二分对于不同的题目有不同的坑点
下面将会对于每道题目具体分析