$$【模板】三分法$$

题目链接：$\mathrm{l}\mathrm{u}\mathrm{o}\mathrm{g}\mathrm{u}\mathrm{P}3382$

题目

如题，给出一个 $N$ 次函数，保证在范围 $[l,r]$ 内存在一点 $x$ ，使得 $[l,x]$ 上单调增， $[x,r]$ 上单调减。试求出 $x$ 的值。

输入

第一行一次包含一个正整数 $N$ 和两个实数 $l,r$ ，含义如题目描述所示。

第二行包含 $N+1$ 个实数，从高到低依次表示该 $N$ 次函数各项的系数。

输出

输出为一行，包含一个实数，即为 $x$ 的值。四舍五入保留 $5$ 位小数。

样例输入

3 -0.9981 0.5
1 -3 -3 1

样例输出

-0.41421

样例解释

如图所示，红色段即为该函数 $f(x)=x^3-3x^2-3x+1$ 在区间 $[-0.9981,0.5]$ 上的图像。

当 $x=-0.41421$ 时图像位于最高点，故此时函数在 $[l,x]$ 上单调增， $[x,r]$ 上单调减，故 $x=-0.41421$ ，输出 $-0.41421$ 。

（Tip. $l\&r$ 的范围并不是非常大ww不会超过一位数）

思路

这道题是三分模板题。

三分的主要思想就是每次找两个点，然后看得出来的函数值谁大，那就有两种情况：

1. 左边的大，那就是这两张图的其中一个
   那我们可以发现，最高点一定不再右边点的右边。
2. 右边的大，那就是这两张图的其中一个
   
   
   那我们可以发现，最高点一定不再左边点的左边。

（其实如果两个点的值相同，那就只能是两个点中间的部分了）

那我们就可以通过这种方法来不断的缩小范围，每次找一个 $mid$ ，然后拿它左边一点和右边一点的点来比较，就可以用差不多是 $logn$ 的时间复杂度求出答案。

不过判断结束的时候不要弄 $l>r$ 或者 $l>=r$ ，因为是三分，这样会退不出去。应该把范围弄大一点，然后三分完之后再直接暴力枚举剩下那个小区间的每个点，找到最高点。

还有因为这一道题是要小数的，那在三分的时候我们可以先乘 $100000$ ，然后计算函数值和输出的时候再除回去。

代码

#include<cstdio>
#define chuli 100000
#define eps 1e-7

using namespace std;

int n, l, r;
double L, R, a[14], mid, minn = -2147483647, minx;

double getans(double x) {//得出这个x对应的值
	double re = 0, now = 1;
	for (int i = 1; i <= n + 1; i++) {
		re += now * a[n - i + 2];
		now *= x;
	}
	return re;
}

int main() {
	scanf("%d %lf %lf", &n, &L, &R);//读入
	for (int i = 1; i <= n + 1; i++) scanf("%lf", &a[i]);
	
	l = (int)(L * chuli);
	r = (int)(R * chuli);
	while (r - l > 50) {//三分
		int mid = (l + r) / 2;
		double X = getans(((double)mid) / chuli - eps), Y = getans(((double)mid) / chuli + eps);//得到中间值两边的x对应的值
		if (X > Y) {//左边的值比右边的大
			r = mid;
		}
		else if (X < Y) {//左边的值比右边的小
			l = mid;
		}
	}
	
	for (int i = l; i <= r; i++) {//剩下一个小范围的直接枚举全部
		double now = getans(((double)i) / chuli);
		if (now > minn) {
			minn = now;
			minx = i;
		}
	}
	
	printf("%.5lf", ((double)minx) / chuli);//输出
	
	return 0;
}