三分查找

问题

题目链接

三分查找的主要用途是用来求解区间最大最小值问题

此类问题有两种解法，解法一 三分查找， 解法二 数学求导

AC Code

#include <bits/stdc++.h>
#define debug(x) cout << #x << ' ' << x << '\n'
#define endl '\n'

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
const int N = 100010, mod = 1e9 + 7, inf = 0x3f3f3f3f;
const double eps = 1e-6;

double n, l, r;
double X[N];

double f(double x)
{
    double sum = 0;
    for(int i = 0; i <= n; i++)
        sum += X[i] * pow(x, n - i);

    return sum;
}

void solve()
{
    cin >> n >> l >> r;
    for(int i = 0; i <= n; i ++)
        cin >> X[i];

    double mid, m1, m2;
    while(eps < r - l)
    {
        mid = (r - l) / 3.0;
        m1 = l + mid, m2 = r - mid;
        if(f(m1) >= f(m2)) r = m2;
        else l = m1;
    }
    cout << l << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    solve();

    return 0;
}