【【模板】三分法】

【模板】三分法

题意

给出一个N次函数，保证在范围\([l,r]\)内存在一点\(x\)，使得\([l,x]\)上单调增，

在\([x,r]\)单调减，求\(x\)的值。

思路

三分模板

代码

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1e5+10;
const double eps=1e-6;
typedef long long ll;
typedef unsigned long long ull;

int n;
double arr[N];
double judge(double x)
{
    double tmp=1.0,ans=0.0;
    for(int i=n;i>=0;i--,tmp*=x) ans+=arr[i]*tmp;
    return ans;
}
int main()
{
    double L,R;
    scanf("%d%lf%lf",&n,&L,&R);
    for(int i=0;i<=n;i++) scanf("%lf",&arr[i]);
    while(R-L>eps)
    {
        double m1=L+(R-L)/3;
        double m2=R-(R-L)/3;
        if(judge(m1)>judge(m2)) R=m2;
        else L=m1;
    }
    printf("%.5lf\n",L);
//  printf("%.5lf\n",(L+R)/2);
    return 0;
}