这个图很好

很好助于理解

假设我二分斜率

这里红色的线就是每点的直线

每条直线的表达式是 y = k（ x - x‘） + g（x’）

我只要求出在 x = k处y的最大值是过哪个点的

我就可以直接斜率该怎么调整

因为这个最大是 过小于k 的点做出来的

说明现在斜率太大了

所以我应该斜率变小

同理

如果是 >k 的点取到了 max

是不是说明斜率太小了

所以我可以根据最后的答案是那个点取到的，来调整斜率， 最后相切在x = k处

然后我们现在来看这个答案该怎么算

y = k（ x - x‘） + g（x’）

我要算所有直线在 x = K 时候的最大值

把x = K 代入

y = k * K - k * x‘ + g（x’）

g（x’） - k*x‘

g（x'）是取 x’ 次的最大值

所以如果我让所有物品都减掉 k

再求出的 g（x‘）

是不是 已经 减掉了 k * x’

然后 求出最大值后最加上 k* K

就是y 的最大值

所以变成无限制

然后wqs要注意的地方

就是三点一线

这种情况

我们应该让 每次取到最左端或者最右端

因为凸壳不应该有三点共线

所以固定取一端

而且共线的点， 他们直线在 x = k 的贡献都是一样的