P3382 【模板】三分法
题目描述
如题，给出一个N次函数，保证在范围[l,r]内存在一点x，使得[l,x]上单调增，[x,r]上单调减。试求出x的值。
输入输出格式
输入格式：
第一行一次包含一个正整数N和两个实数l、r，含义如题目描述所示。
第二行包含N+1个实数，从高到低依次表示该N次函数各项的系数。
输出格式：
输出为一行，包含一个实数，即为x的值。四舍五入保留5位小数。
输入输出样例
说明
时空限制：50ms,128M
数据规模：
对于100%的数据：7<=N<=13
样例说明：
如图所示，红色段即为该函数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不会超过一位数）
单调函数具有单调性，用二分解决。当单调增减同时位于一个高次函数中，则用三分。
三分实质上就是两次二分，用来寻找图像的波峰或波谷。
#include <bits/stdc++.h> #define MAX 15 #define e 0.0000001 using namespace std; typedef long long ll; int n; double a[MAX]; double f(double x){ double ans=a[0];double mul=1; for(int i=1;i<=n;i++){ mul*=x; ans+=a[i]*mul; } return ans; } int main(void) { int i,j; double l,r,m,mm; scanf("%d%lf%lf",&n,&l,&r); for(i=n;i>=0;i--){ scanf("%lf",&a[i]); } while(r-l>e){ m=(l+r)/2.0; mm=(m+r)/2.0; if(f(m)<f(mm)) l=m; else r=mm; } printf("%.5f ",l); return 0; }