洛谷-P3382 三分 题解

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

题解：单峰函数极值点的三分查找

题目大意

给定一个 N 次多项式函数

f(x) = a0 x^N + a1 x^(N-1) + ... + a（N-1）x + aN

（输入顺序为从高次项到常数项），并保证在区间 [l, r]上存在唯一一点 x，使得：

• 在 [l, x] 上函数单调递增；
• 在 [x, r]上函数单调递减。

即：函数在 [l, r]上是严格单峰的，存在唯一极大值点。

要求：求出该极大值点 x 的值，满足与标准答案的绝对或相对误差不超过 10^(-5)，或其对应的函数值误差满足该条件。

解题思路

由于函数在给定区间上是单峰函数（先增后减），其图像呈“山峰”形状，因此可以使用三分法（Ternary Search） 来高效逼近极大值点。

三分法原理简述

在区间 [l, r] 中取两个三等分点：

• mid_1 = l + (r - l)/3
• mid_2 = r - (r - l)/3

比较 f(mid_1)与 f(mid_2)：

• 若 f(mid_1) < f(mid_2)，说明极大值点在 [mid_1, r]，令 l = mid_1；
• 否则，极大值点在 [l, mid_2]，令 r = mid_2。

不断缩小区间，直到区间长度小于精度要求（如 10^{-6}），此时区间内任意点均可作为答案。

源代码

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

vector<double> vec = vector<double>(15);
double eps = 1e-6;
int n;

double func(double x)
{
    double ans = 0;
    for (int i = 0; i <= n; i++)
        ans = vec[i] + x * ans;
    return ans;
}

int main()
{
    double l, r;
    cin >> n >> l >> r;
    for (int i = 0; i <= n; i++)
        cin >> vec[i];

    double mid1, mid2;
    while (r - l > eps)
    {
        mid1 = l + (r - l) / 3;
        mid2 = r - (r - l) / 3;
        if (func(mid1) < func(mid2))
            l = mid1;
        else
            r = mid2;
    }

    cout << fixed << setprecision(5) << r << endl;
    return 0;
}

复杂度分析

• 时间复杂度：每次迭代将区间缩小为原来的 2/3，达到精度 10^（-6） 约需 50 到 70 次迭代。每次 func 调用耗时 O(N)，总时间复杂度为 O(N*log1/ε)，完全可接受。
• 空间复杂度：O(N)，仅存储多项式系数。

总结

本题利用单峰函数性质，采用经典的三分查找方法，在保证精度的前提下高效求解极大值点。