[洛谷]P3382 三分 | CloudingYu的博客

题目描述

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

输入格式

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

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

样例输入
3 -0.9981 0.5
1 -3 -3 1

输出格

输出为一行，包含一个实数，即为 $x$ 的值。若你的答案与标准答案的相对或绝对误差不超过 $10^{-5}$ 则算正确。

什么是三分法？

三分法类似于二分，原理为不断缩小答案所在的求解区间。

二分缩小区间利用函数的单调性，而三分法利用的则是函数的单峰性。

拿样例来说： $\displaystyle y = x^3 - 3x^2 - 3x + 1$ , $x\in[ -0.9981 , 0.5 ]$ ，需要求出它在该区间的最大值 $max$ :

将 $[ -0.9981 , 0.5 ]$ 均分为三个区间: $[-0.9981,-0.498]$ , $[-0.498,0.00006]$ , $[0.00006,0.5]$ 。

同时得到了两个点 $m_1$ 和 $m_2$ : 我们把 $m_1$ , $m_2$ 中函数值更大的 $m_1$ 称为好点，较小的 $m_2$ 称为坏点。

那么不难发现，好点 $m_1$ 和极值 $max$ 都在坏点 $m_2$ 的左侧，所以可以将搜索的区间缩小为 $[ -0.9981 , 0.00006 ]$ 。( $0.00006$ 即为 $m_2$ 的横坐标) 这样不断缩小搜索的区间，最终就能够获得一个足够小的区间以至接近一个实数值,以达到求值的目的。

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
int n;             // 函数次数
double l, r;       // 左区间和右区间
double t[15];      // 各项系数
double f(double d) // 计算横坐标为d时的函数值
{
    double ans = 0;
    for (int i = n + 1; i >= 1; i--) // 高次向低次计算
    {
        double x = t[i];
        for (int j = 1; j <= i - 1; j++) // 计算每一项的值（注意
            x *= d;
        ans += x; // 相加
    }
    return ans;
}
int main()
{
    cin >> n >> l >> r;              // 读入函数次数，左区间和右区间
    for (int i = n + 1; i >= 1; i--) // 读入函数各项系数
        cin >> t[i];
    double lmid, rmid;
    while (r - l > 0.00000001)
    {
        lmid = l + (r - l) / 3; // 相当于上面的m1的横坐标
        rmid = r - (r - l) / 3; // 相当于上面的m2的横坐标
        if (f(lmid) < f(rmid))  // 比较m1,m2哪个是好点，哪个是坏点
            l = lmid;           // 若m1是坏点，将左区间更新为m1的横坐标
        else
            r = rmid; // 若m2是坏点，将右区间更新为m2的横坐标
    }
    printf("%0.5lf\n", r); // 保留5位小数输出
    return 0;
}

加一减一的细节要注意