三分搜索
二分搜索一般用于寻找正好满足某种条件的临界值,要求搜索区间满足单调性,而三分搜索一般是在凸函数或者凹函数上寻找极值。
原理
假设函数图像在区间[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是三个相邻的整数,分别计算函数在这三个点的取值,取三者的极值即可。