写在之前

今天学习了三分法

真的好好用 回去直接把模板切了

正式开始

三分法就是单峰函数求最值

当前我们位于\([le,ri]\)

然后我们我们有两个三等分点\(mid,mmid(mid<mmid)\)

假设我们求最大值

我们比较\(f(mid)\)以及\(f(mmid)\)

\(1.f(mid)>f(mmid)\)

那么可以确定的是\(mmid\)一定位于极值点右边

证明 : 画图之后显然啊

\(2.f(mid)<f(mmid)\)

那么可以确定的是\(mid\)一定位于极值点左边

证明 : 画图之后显然啊

然后乖乖写代码就可以了

CODE:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<list>
#include<set>
#include<deque>
#include<vector>
#include<ctime>
#define ll long long
#define inf 0x7fffffff
#define N 500008
#define IL inline
#define M 1008611
#define D double
#define eps 1e-7
#define R register
using namespace std;
template<typename T>IL void read(T &_)
{
    T __=0,___=1;char ____=getchar();
    while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}
    while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}
    _=___ ? __:-__;
}
/*-------------OI使我快乐-------------*/
int n;D le,ri;
D f[N];
IL D qpow(D x,int y)
{D res=1;for(;y;y>>=1,x=x*x)if(y&1) res=res*x;return res;}
IL D work(D x)
{
    D res=0;
    for(R int i=n;i>=0;--i)
    res+=qpow(x,i)*f[i];
    return res;
}
int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    read(n);scanf("%lf%lf",&le,&ri);
    for(R int i=n;i;--i) scanf("%lf",&f[i]);
    while(ri-le>eps)
    {
        D mid=(le+ri)/2.0,mmid=(mid+ri)/2.0;
        D cdy=work(mid),wzy=work(mmid);
        if(cdy>wzy) ri=mmid;
        else le=mid;
    }
    printf("%.5f\n",le);
//	fclose(stdin);
//	fclose(stdout);
    return 0;
}