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

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

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

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

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

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

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

可以发现，随着 k k k 的减小，这条直线切的点会越来越靠右，就像这样： （这图也不算太严谨，因为有些点没画，但是能看明白意思就好）

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

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

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

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

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

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

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

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

可能还会更新的qwq

难度大概是递增的。

[国家集训队2]Tree I   题解 [IOI2000]邮局   题解 CF739E Gosha is hunting   题解 忘情   题解