https://loj.ac/problem/6620

高中数学好题。。

|kx+b|的函数图像很直观,直接考虑函数图像:

「THUPC 2019」不等式 / inequality-LMLPHP

一定只有一段极小值点!

这个点就是最小值了

特点:斜率为0!

而且发现,如果每个|kx+b|的零点作为一个端点的话,那么最小值一定可以在一个端点取到!

(因为两个端点之间是一次函数,最值一定是二者之一)

这个最小值点斜率是负的,下一个就是正的

所以线段树维护斜率和、截距和

加入|kx+b|,分成两段,第一段整体+k,+b第二段同理

二分找到最后一个斜率是负数的点

其实,x的k的值是:

「THUPC 2019」不等式 / inequality-LMLPHP

黑色是最后函数图像,

红色的斜率是两个相邻黑边的斜率平均值

05-15 22:14