p3382

题目分析

题目要求在一个区间 内找到一个点 ，使得给定的 次函数在 上单调递增，在 上单调递减。根据题目描述，这样的点 是函数在区间 上的极大值点（即函数在该点取得局部最大值）。题目保证在 内存在唯一这样的点。

解题思路

由于函数在 单调递增，在 单调递减，整个区间上函数呈现单峰形态（先增后减）。因此，我们可以使用三分法（Ternary Search）来高效地找到这个极大值点 。

• 三分法原理：
  在单峰函数中，极大值点将区间分为两部分：左侧单调递增，右侧单调递减。三分法通过不断缩小区间来逼近极大值点：

  1. 将当前区间 分成三等份，取两个中间点：
     
  2. 比较函数值 和 ：
     • 如果 ，则极大值点一定在 内，因此更新 。
     • 否则，极大值点一定在 内，因此更新 。
  3. 重复上述过程直到区间足够小（例如迭代固定次数），最终区间中点即为所求 。

• 多项式求值优化：
  使用Horner 方法（秦九韶算法）高效计算多项式值。对于多项式 ，Horner 方法将其转化为：

  

  这种方法只需 时间，且能减少浮点运算的精度误差。

• 精度处理：

  • 迭代次数：固定 100 次迭代可将区间缩小到初始长度的 ，远超题目要求的 精度。
  • 输出：保留 10 位小数，确保满足绝对或相对误差 。
  • 函数值比较：直接比较浮点数，依赖三分法的收敛性。

算法步骤

1. 输入处理：
   • 读取整数 和实数 。
   • 读取 个系数（从高次到低次），存储在数组 coeff 中。
2. 定义多项式求值函数：
   • 使用 Horner 方法计算 。
3. 三分法求解：
   • 初始化区间 。
   • 迭代 100 次：
     • 计算 和 。
     • 计算 和 。
     • 根据比较结果缩小区间。
   • 取最终区间的中点作为答案 。
4. 输出结果：以 10 位小数精度输出 。

代码实现

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

typedef double db;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    db l, r;
    cin >> N >> l >> r;
    vector<db> coeff(N + 1);
    for (int i = 0; i <= N; i++) {
        cin >> coeff[i];
    }
    
    auto f = [&](db x) -> db {
        db res = 0.0;
        for (int i = 0; i <= N; i++) {
            res = res * x + coeff[i];
        }
        return res;
    };
    
    db left = l, right = r;
    for (int i = 0; i < 100; i++) {
        db mid1 = left + (right - left) / 3.0;
        db mid2 = right - (right - left) / 3.0;
        db f1 = f(mid1);
        db f2 = f(mid2);
        if (f1 < f2) {
            left = mid1;
        } else {
            right = mid2;
        }
    }
    
    db ans = (left + right) / 2.0;
    printf("%.10f\n", ans);
    
    return 0;
}

复杂度分析

• 时间复杂度：，其中 是迭代次数（固定为 100）， 是多项式次数。每次迭代计算两个函数值，每次求值 。
• 空间复杂度：，用于存储多项式系数。

注意事项

1. 精度问题： 单峰保证：题目保证函数在 上单峰，三分法适用。
2. 边界情况：当 时，算法选择缩小区间右半部分（else 分支），这不会影响收敛性。