[JZOJ4640] 【GDOI2017模拟7.15】妖怪

题目

描述

题目大意

给你一堆$a_i$和$b_i$（方便起见用的变量和上面不一样），让你搞出一个$x$（相当于题目中的$frac{b}{a}$，随便推推就能知道），
使得$max a_i+b_i+a_ix+frac{b_i}{x}$最小。

---

思考历程

第一眼看下去，最大最小放一起，显然就是一个二分啊！
然后开始想……想不出来，推了个式子，感觉似乎要三分套三分套三分……
更气的是这题还不好打暴力。
所以推了很久之后什么都没有打。

---

正解

其实这个题目的正解有好几种。

先说二分的做法（WMY大佬的方法，只可惜被卡了常数）：
首先我们二分答案，然后判断是否可行。
要满足$a_i+b_i+a_ix+frac{b_i}{x}leq ans$，
变化一下式子：$a_ix^2+(a_i+b_i-ans)x+b_ileq 0$
发现可以用一元二次方程的方法来解，
于是对于每个$a_i$和$b_i$，我们都可以得出一个解集。
然后取它们的交集，如果不为空就成立。
正确性显然。

再说三分的做法：
首先有个重要的结论：$y=a_i+b_i+a_ix+frac{b_i}{x}$的图像是一个单峰函数（$V$字形，左边陡，右边缓）。
LYL给出了一个很强的证明：
首先$a_i+b_i$是定值，先不理它，只考虑$y=a_ix+frac{b_i}{x}$
变化式子：$a_ix^2-yx+b_i=0$
一元二次方程！然后算出$Delta=y^2-4a_ib_i$，解为$x=frac{y pmsqrt{y^2-4a_ib_i}}{2a}$
这时候就可以脑补出它的图像了……
显然，方程的解只有一个的时候就是顶点，所以顶点为$(frac{sqrt{ab}}{a},2sqrt{ab})$
还有YMQ的证明：
将$y$除以$a_i$，设$c_i=frac{b_i}{a_i}$，则$y=x+frac{c_i}{x}$
这就相当于反比例函数上的纵坐标和横坐标之和！
显然在直线$y=x$上最优……（具体证明可以用基本不等式）
整理一下，当$x=frac{sqrt{ab}}{a}$时最优。
证明完了，下面是做法：
对于每个$i$，都会有一个图象。将它们放在一起，取$max$，可以发现图象是单峰（谷）的。
考虑反证，如果图象为$W$形，那么中间交接的那个地方实际上可以继续延伸，在上面更高的地方形成$V$形，所以不可能会出现$W$形。
所以三分出最低点就可以了。

还有一种方法是最优秀的线性方法。
考虑斜率优化。
假设$a_i<a_j$且$y_i<y_j$，那么$a_i+b_i+a_ix+frac{b_i}{x}<a_j+b_j+a_jx+frac{b_j}{x}$
变化式子：$T(i,j)=-frac{b_i-b_j}{a_i-a_j}<x$（$T$只是为了后面方便表示）
然后就可以斜率优化了！
先处理出一个斜率递增的序列，对于序列上的每个点$i$，在$xin [T(i-1,i),T(i,i+1)]$时，$y_i$是最大的。
所以求出$x$在这个区间内$y_i$的最小值就好了。
将$y_i$的$V$形图象画出来，就可以发现这个区间的位置及对应的最小值的情况。
在顶点左边，跨过顶点，在顶点右边三种情况分类讨论。
这就可以$O(1)$求出它的最小值。
总的来说，这个方法是线性的。

---

代码

线性做法（我只打了线性的）

using namespace std;
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
inline int input(){
	char ch=getchar();
	while (ch<'0' || '9'<ch)
		ch=getchar();
	int x=0;
	do{
		x=x*10+ch-'0';
		ch=getchar();
	}
	while ('0'<=ch && ch<='9');
	return x;
}
#define N 1000010
int n;
struct Monster{
	int a,b;
} d[N];
inline bool cmpd(const Monster &x,const Monster &y){
	return x.a<y.a || x.a==y.a && x.b>y.b;
}
int q[N],head,tail;
inline bool pd(int i,int j,int k){
	return -(long long)(d[i].b-d[j].b)*(d[j].a-d[k].a)>=-(long long)(d[j].b-d[k].b)*(d[i].a-d[j].a);
}
inline double calc(int i,int j){
	return -(double)(d[i].b-d[j].b)/(d[i].a-d[j].a);
}
inline double get(int k,double l,double r){
	if (l-r>1e-8)
		return 1e8;
	double mn=sqrt(1ll*d[k].a*d[k].b)/d[k].a;
	if (r<mn)
		return d[k].a+d[k].b+d[k].a*r+d[k].b/r;
	if (l>mn)
		return d[k].a+d[k].b+d[k].a*l+d[k].b/l;
	return d[k].a+d[k].b+d[k].a*mn+d[k].b/mn;
}
int main(){
	n=input();
	for (int i=1;i<=n;++i)
		d[i]={input(),input()};
	sort(d+1,d+n+1,cmpd);
	for (int i=1;i<=n;++i){
		while (head<tail && pd(q[tail-1],q[tail],i))
			tail--;
		q[++tail]=i;
	}
	double ans=get(q[1],1e-4,calc(q[1],q[2]));
	for (int i=2;i<tail;++i)
		ans=min(ans,get(q[i],calc(q[i-1],q[i]),calc(q[i],q[i+1])));
	ans=min(ans,get(q[tail],calc(q[tail-1],q[tail]),1e8));
	printf("%.4lf",ans);
	return 0;
}

自认为讲解得比较清晰，就不打注释了。

---

总结

面对这样有关式子和最值的题目，二分和三分都是很好的思考方向。
有时候还可以尝试一下斜率优化。
最后我们认识了这样的函数$y=ax+frac{b}{x}$，它的顶点在$(frac{sqrt{ab}}{a},2sqrt{ab})$