题目描述:令$\max\{atk_i+dnf_i+\frac{dnf_i*a}{b}+\frac{atk_i*b}{a}\}$最小。

通过观察,可以发现具体的$a,b$不用求,只要利用相对值$\frac{a}{b}$即可。

观察柿子,对于每一个$i$,其实就是一个对勾函数(单峰的)。

网上有一种说法就是三分,也就是多个对勾函数取最大值之后还是单峰的。

但是我不会,所以我还是老老实实写凸包。

考虑当$i$成为最大值时,$\frac{a}{b}$定然有一个取值范围才使得$i$成为最大值。

那么可以构想,必然存在于上凸包的点才会对最大值产生贡献。

这个很好理解,一个$atk(x),dnf(y) $都小于其他的点的点,没有贡献的价值。

另外,若$\frac{a}{b}<0$,则无最大值可言。

那么$\frac{a}{b}$的取值范围究竟是多少,也就是要计算临界值。

这里就用$i-1$来描述一下吧,也就是凸包上前一个点。

$k=\frac{b}{a},(1+k)x_i+(1+\frac{1}{k})y_i=(1+k)x_{i-1}+(1+\frac{1}{k})y_{i-1}$

存在解:$k=\frac{y_{i-1}-y_{i}}{x_i-x_{i-1}}$,左端点的$\frac{b}{a}$已得出。

学过对勾函数的都知道,一段连续的区间,最小值要么在左端点,要么在右端点,要么在$\sqrt{\frac{y_i}{x_i}}$(视情况取)。

差不多了。