三分搜索

二分搜索一般用于寻找正好满足某种条件的临界值,要求搜索区间满足单调性,而三分搜索一般是在凸函数或者凹函数上寻找极值。

原理

假设函数图像在区间[lo,hi]是开口向上的曲线,那么区间内必有极大值,取三分点m1和m2,若f(m1)>f(m2),那么极大值位于[lo,m2]内,排除区间[m2,hi];反之极大值区于[m1,hi]内,可排除[lo,m1],时间复杂度为O(logn)。

51nod1629 B君的圆锥

题面:已知圆锥的表面积为S,求它的体积V的最大值。

分析:设圆锥半径为r,由于表面积S固定,直观上看,当r很小时圆锥虽然高,但太瘦,导致体积小;当r很大时圆锥胖,但太矮,体积也不大;应取合适的r值,使宽度和高度平衡,方能取到最大体积。

#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
int s;
double getl(double r) {
    return (s - pi * r * r) / pi / r;
}
double geth(double r) {
    double l = getl(r);
    return sqrt(l * l - r * r);
}
double vol(double r) {
    double h = geth(r);
    return pi * r * r * h / 3;
}
int main() {
    cin >> s;
    double lo = 0, hi = sqrt(s/2/pi);
    while (hi - lo > 1e-6) {
        double m1 = lo + (hi - lo) / 3;
        double m2 = lo + (hi - lo) / 3 * 2;
        double v1 = vol(m1), v2 = vol(m2);
        if (v1 > v2)
            hi = m2;
        else
            lo = m1;
    }
    printf("%.6f\n", vol(lo));
    return 0;
}

奶牛的聚会

题面:在x轴上有n个点,给定第i个点的坐标x[i]和权值w[i],需要在x轴上选一点d,使得sum(w[i]*|d-x[i]|^3)最小,求该最小值。

分析:d过于偏左或者偏右都会导致结果太大,应该在中间某处取,使得左右两边的带权距离平衡,以获得最小值。

#include <bits/stdc++.h>
using namespace std;
int n, T;
double x[50005], w[50005];
double f(double d) {
    double ret = 0;
    for (int i = 1; i <= n; i++) {
        double u = fabs(d - x[i]);
        ret += u * u * u * w[i];
    }
    return ret;
}
int main() {
    cin >> T;
    for (int z = 1; z <= T; z++) {
        double lo = 1e6, hi = -1e6, ans = 9e18;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> x[i] >> w[i];
            lo = min(lo, x[i]);
            hi = max(hi, x[i]);
        }
        if (n == 1) {
            ans = 0;
        } else {
            while (hi - lo > 1e-6) {
                double m1 = lo + (hi - lo) / 3;
                double m2 = lo + (hi - lo) / 3 * 2;
                double v1 = f(m1), v2 = f(m2);
                if (v1 < v2)
                    hi = m2, ans = v1;
                else
                    lo = m1, ans = v2;
            }
        }
        printf("Case #%d: %d\n", z, int(ans + 0.5));
    }
    return 0;
}

在整数内搜索

上面两个例子都是在实数范围内做三分搜索,当搜索区间长度小于指定精度时则停止。

如果要求取值必须为整数,三分搜索同样可以工作,区别在于循环终止时的处理:当lo+2等于hi时停止搜索,此时m1=m2,且lo,m1,hi是三个相邻的整数,分别计算函数在这三个点的取值,取三者的极值即可。

Table of Contents