洛谷 P3382（三分查找凹点和凸点）

题目链接：https://www.luogu.org/problem/P3382

题目描述
如题，给出一个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

说明/提示
时空限制：50ms,128M

数据规模：

对于100%的数据：7<=N<=13

样例说明：

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

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

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

三分的知识点：

已知：左右端点L、R，要求找到上图中空心点的位置

思路：通过不断缩小 [L,R] 的范围，无限逼近空心点

思想：先取 [L,R] 的中点 mid，再取 [mid,R] 的中点 mmid，通过比较 f(mid) 与 f(mmid) 的大小来缩小范围。
当最后 L=R-1 时，再比较下这两个点的值，我们就找到了答案。
1、当 f(mid) > f(mmid) 的时候，我们可以断定 mmid 一定在空心点的右边。
反证法：假设 mmid 在白点的左边，则 mid 也一定在白点的左边，又由 f(mid) > f(mmid) 可推出 mmid < mid，与已知矛盾，故假设不成立。
所以，此时可以将 R = mmid 来缩小范围。
2、当 f(mid) < f(mmid) 的时候，我们可以断定 mid 一定在空心点的左边。
反证法：假设 mid 在白点的右边，则 mmid 也一定在白点的右边，又由 f(mid) < f(mmid) 可推出 mid > mmid，与已知矛盾，故假设不成立。
同理，此时可以将 L = mid 来缩小范围

利用此思想可以用三分找到空心点的位置
代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define eps 1e-12
int n;
double l,r,a[20];
double solve(double x)
{
    double ans=1,sum=0;
    for(int i=n+1; i>=1; i--)
    {
        sum+=ans*a[i];
        ans*=x;
    }/*传过来的x相当于函数表达式中的未知量，将未知量代入表达式，求得函数表达式的最终结果*/
    return sum;
}
int main()
{
    scanf("%d%lf%lf",&n,&l,&r);
    for(int i=1; i<=n+1; i++)
        scanf("%lf",&a[i]);
    while(r-l>=eps)
    {
        double mid=l+(r-l)/3;
        double mmid=r-(r-l)/3;
        if(solve(mid)-solve(mmid)>=eps)
            r=mmid;/*一步步缩小范围*/
        else
            l=mid;
    }
    printf("%.5lf\n",l);
    return 0;
}

祝祖国繁荣昌盛