二分

通过二分来逼近答案

浮点数

求 mid 使 f(mid) = y
f(x)满足单调递增

1
2
3
4
5
6
7
8
9
10
11
double high,low,mid;
while(high - low > eps)
{
mid = (high + mid)/2;
if(cal(mid) < y)
low = mid;
else
high = mid;
}

return (low + high)/2;

二分答案

1
2
3
4
5
6
7
8
9
10
11
12
13
int high,low,res;
while(low <= high)
{
int mid = (high+low)>>1;
if(ok(mid))
{
low = mid + 1;
res = mid;
}
else high = mid - 1;
}

return res;

三分

求凸性/凹性函数的极值

凸性函数

mid = (left + right)/2;
midmid = (mid + right)/2;
mid 靠近极值点 right = midmid;
否则(midmid靠近极值点) left = mid;

1
2
3
4
5
6
7
8
9
10
11
12
13
double high,low,mid,midmid;
while(high - low > eps)
{
mid = (low + high)/2;
midmid = (mid + high)/2;
double fmid = f(mid) , fmidmid = f(midmid);
if( fmid > fmidmid)
high = midmid;
else
low = mid;
}

return (low+high)/2;
  • 一般设置迭代次数避免超时…

整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int high,low,mid,midmid,res;
while(low <= high)
{
mid = (high + low)/2;
midmid = (mid + high)/2;
int cmid = cal(mid) , cmidmid = cal(midmid);
if( cmid >= cmidmid )
{
res = mid;
high = midmid-1;
}
else
{
res = midmid;
low = mid+1;
}
}

return res;

题目

hdu3756

求最小体积的圆锥覆盖空间内所有的点。
我们将圆锥和点映射到x-z平面,
然后就是一条在y轴截距为h,x轴截距为R的直线
我们二分高度h,根据每个点的位置通过斜率求出对应最大的R
对应函数为 V = hRR

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>

using namespace std;

const int maxn = 10010;
double X[maxn],Y[maxn];
double INF = 1e10;
double eps = 1e-9;
int n;

double getR(double h)
{
double R = 0;
for(int i=0;i<n;++i)
{
if(R*(h-Y[i])<h*X[i])
R = X[i]*h/(h-Y[i]);
}
return R;
}

void solve(double l)
{
double low = l ,high = INF;
while(high - low > eps)
{
double mid = (low+high)/2;
double mmid = (mid + high)/2;
double R0 = getR(mid),R1 = getR(mmid);
if(R0*R0*mid < R1*R1*mmid)
{
high = mmid;
}
else
{
low = mid;
}
}
printf("%.3lf %.3lf\n",low+eps,getR(low)+eps);
}


int main()
{
//freopen("test.txt","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
double l = 0;
for(int i=0;i<n;++i)
{
double x,y,z;
scanf("%lf%lf%lf",&x,&y,&z);
X[i] = sqrt(x*x+y*y);
Y[i] = z;
l = max(l,z);
}
solve(l);
}
return 0;
}