本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15704448.html

二分

对于一个存在单调性的函数，我们要枚举满足条件的最小/最大值，我们通过枚举中间值缩小范围来定位。

1
2
3
4
5
6
while(l<r)
{
 mid=(l+r+1)>>1; 
 if(check(mid)) l=mid; 
 else r=mid-1; 
}

三分

对于一个存在单峰/单谷性的函数，我们可以通过枚举两个端点通过比较大小缩小范围求出峰顶/谷底。

1
2
3
4
5
6
7
while(r-l>1e-18)
        {
            lmid=l+(r-l)/3; 
            rmid=r-(r-l)/3; 
            if(check(lmid)>check(rmid)) l=lmid; 
            else r=rmid; 
        }

对于二分和三分，我重点会在例题中讲。

例题1：【Loj #10011. 「一本通 1.2 例 1」愤怒的牛】

题目链接

题目

农夫约翰建造了一座有 间牛舍的小屋，牛舍排在一条直线上，第 间牛舍在 的位置，但是约翰的

头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？农夫约翰建造了一座有 间牛舍的小屋，牛舍排在一条直线上，第 间牛舍在 的位置，但是约翰的

头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。John 决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

思路

首先我们对牛棚从小到大排序。

然后我们二分距离，再暴力检查是否可行。

时间复杂度：O(nlog⁡n)O(n\log n)

Code

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
// Problem: #10011. 「一本通 1.2 例 1」愤怒的牛
// Contest: LibreOJ
// URL: https://loj.ac/p/10011
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
//#define N
int n, m, i, j, k; 
int a[100010]; 
int l, r, mid, now; 

int check(int d)
{
	for(i=2, j=1, now=a[1]; i<=n; ++i)
		if(a[i]-now>=d) ++j, now=a[i]; 
	return j>=m; 
}

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
	n=read(); m=read(); 
	for(i=1; i<=n; ++i) a[i]=read(); 
	sort(a+1, a+n+1); 
	l=0, r=a[n]; 
	while(l<r)
	{
		mid=(l+r+1)>>1; 
		if(check(mid)) l=mid; 
		else r=mid-1; 
	}
	printf("%lld", l);  
	return 0; 
}

例题2：【Loj #10012. 「一本通 1.2 例 2」Best Cow Fences】

题目链接

题目

给定一个长度为 nnn 的非负整数序列 AAA ，求一个平均数最大的，长度不小于 LLL 的子段。

思路

先二分平均值。

然后是判断。

如何判断一段数中是否存在长度大于等于 LL 且平均值大于某个数的子段呢？

我们可以先让序列中的数都减去二分中的值，然后就转化为：

序列中是否存在长度大于等于 LL 的字段和为正。

我们可以先构造一个前缀和。

假设我们当前算到序列中的第 ii 项，我们只需要在前 i−Li-L 项中找最小前缀和，再用 SiS_i 去减即可。如果为正，说明符合条件。

Code

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
// Problem: #10012. 「一本通 1.2 例 2」Best Cow Fences
// Contest: LibreOJ
// URL: https://loj.ac/p/10012
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
#define N 100010
int n, m, i, j, k; 
int len; 
double l, r, mid, mn; 
double sum[N], a[N]; 

int check(double d)
{
	sum[0]=mn=99999999999999; 
	for(i=1; i<=n; ++i)
	{
		sum[i]=(i==1? double(0) : sum[i-1])+a[i]-d; 
		mn=min(mn, sum[max(0, i-len)]); 
		if(sum[i]-mn>0) return 1; 
	}
	if(sum[n]>0) return 1; 
	return 0; 
}

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
	n=read(); len=read(); 
	for(i=1; i<=n; ++i) a[i]=double(read()); 
	l=-1, r=2001; 
	while(r-l>0.000000001)
	{
		// printf("%lf %lf\n", l, r); 
		mid=(l+r)/double(2); 
		if(check(mid)) l=mid; 
		else r=mid; 
	}
	printf("%d", int(r*1000)); 
	return 0; 
}

例题3：【Loj #10013. 「一本通 1.2 例 3」曲线】

题目链接

题目

明明做作业的时候遇到了 nnn 个二次函数 Si(x)=ax2+bx+cS_i(x)= ax^2 + bx + cS​i​​(x)=ax​2​​+bx+c，他突发奇想设计了一个新的函数 F(x)=max{Si(x)},i=1…nF(x) = max{S_i(x)}, i = 1ldots nF(x)=max{S​i​​(x)},i=1…n。

明明现在想求这个函数在 [0,1000][0,1000][0,1000] 的最小值，要求精确到小数点后四位，四舍五入。

思路

三分模板。

在区间 [0,1000][0, 1000] 中进行三分，每次 O(n)O(n) 算出答案。

显然， 由于 ss 函数满足单调性，ff 函数是 ss 函数中的最大值，必然也满足单调性。

Code

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
// Problem: #10013. 「一本通 1.2 例 3」曲线
// Contest: LibreOJ
// URL: https://loj.ac/p/10013
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define N
//#define M
//#define mo
int n, m, i, j, k, t; 
double l, r, lmid, rmid, sum; 
double a[100010], b[100010], c[100010]; 

double check(double x)
{
	sum=-99999999999; 
	for(i=1; i<=n; ++i)
		sum=max(sum, a[i]*x*x+b[i]*x+c[i]); 
	return sum; 
}

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	t=read();
	while(t--)
	{
		n=read(); 
		for(i=1; i<=n; ++i)
			scanf("%lf%lf%lf", &a[i], &b[i], &c[i]); 
		l=0; r=1000; 
		while(r-l>0.00000000001)
		{
			lmid=l+(r-l)/3; 
			rmid=r-(r-l)/3; 
			if(check(lmid)>check(rmid)) l=lmid; 
			else r=rmid; 
		}
		printf("%.4lf\n", check(l)); 
	}
	return 0;
}

例题4：【P1182 数列分段 Section II】

题目链接

题目

对于给定的一个长度为N的正整数数列 A1∼NA_{1\sim N}，现要将其分成 MM（M≤NM\leq N）段，并要求每段连续，且每段和的最大值最小。

关于最大值最小：

例如一数列 4 2 4 5 14\ 2\ 4\ 5\ 1 要分成 33 段。

将其如下分段：

[4 2][4 5][1][4\ 2][4\ 5][1]

第一段和为 66，第 22 段和为 99，第 33 段和为 11，和最大值为 99。

将其如下分段：

[4][2 4][5 1][4][2\ 4][5\ 1]

第一段和为 44，第 22 段和为 66，第 33 段和为 66，和最大值为 66。

并且无论如何分段，最大值不会小于 66。

所以可以得到要将数列 4 2 4 5 14\ 2\ 4\ 5\ 1 要分成 33 段，每段和的最大值最小为 66。

思路

二分最小值，然后我们对于每次二分的值进行判断，于是就转换为：

给出一个序列，每段和的最大值不得超过 midmid，问最多能分出多少段。

如果段数超过 kk，说明可行。

时间复杂度 O(nlog⁡n)O(n\log n)

由于这道题是我2021.8做的，所以那时码风很现在的不太一样。

Code

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
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
int n,m,i,j,k;
int a[1000010];
int sum,now,t;
int l,r,mid;

int pan(int x)
{
	now=0;
	t=1;
	for(i=1;i<=n;++i)
	{
		if(a[i]>x)
			return 0;
		if(now+a[i]>x)
		{
			now=a[i];
			++t;
			if(t>m)
				return 0;
		}
		else
			now+=a[i];
	}
	return 1;
}

signed main()
{
//	freopen("seqseg.in","r",stdin);
//	freopen("seqseg.out","w",stdout);
//	std::ios::sync_with_stdio(false);
	n=read();
	m=read();
	for(i=1;i<=n;++i)
		a[i]=read(),sum+=a[i];
	l=0,r=sum;
	while(l<=r)
	{
		mid=l+r>>1;
		if(pan(mid))
			r=mid-1;
		else
			l=mid+1;
	}
//	for(int i=1;i<=sum;++i)
//		printf("%d: %d\n",i,pan(i));
	printf("%d",l);
	return 0;
}

例题5：【P1661 扩散】

题目链接

题目

一个点每过一个单位时间就会向四个方向扩散一个距离，如图。

两个点a、b连通，记作e(a,b),当且仅当a、b的扩散区域有公共部分。连通块的定义是块内的任意两个点u、v都必定存在路径e(u,a0),e(a0,a1),…,e(ak,v)。给定平面上的n给点，问最早什么时刻它们形成一个连通块。

思路

二分答案+并查集。

首先二分时间 tt。

如果两个点能直接相连，则他们的曼哈顿距离小于二倍 tt。并且把他们放到一个并查集里面。

最后判断所有点是否在一个并查集里即可。

Code

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
// Problem: P1661 扩散
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1661
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define N 55 
//#define M
//#define mo
int n, m, i, j, k; 
int x[N], y[N], f[N], l, r, mid; 

int fa(int x)
{
	if(f[x]==x) return x; 
	return f[x]=fa(f[x]); 
}

int check(int t)
{
	for(i=1; i<=n; ++i) f[i]=i; 
	for(i=1; i<=n; ++i)
		for(j=i+1; j<=n; ++j)
			if(abs(x[i]-x[j])+abs(y[i]-y[j])<=2*t)
				f[fa(i)]=fa(j); 
	for(i=2; i<=n; ++i)
		if(fa(i)!=fa(i-1)) return 0; 
	return 1; 
}

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	n=read(); 
	for(i=1; i<=n; ++i)
		x[i]=read(), y[i]=read(); 
	l=1, r=1000000000000; 
	while(l<r)
	{
		mid=(l+r)>>1; 
		if(check(mid)) r=mid; 
		else l=mid+1; 
	}
	printf("%lld", l); 
	return 0;
}

例题6：【P5931 [清华集训2015]灯泡】

题目链接

题目

相比 WildleopardWildleopard 的家，他的弟弟 MildleopardMildleopard 比较穷。他的房子是狭窄的，而且在他的房间里仅有一个灯泡。每天晚上，他徘徊在自己狭小的房子里，思考如何赚更多的钱。有一天，他发现他的影子的长度随着他在灯泡和墙壁之间走动时会发生变化。一个突然的想法出现在他的脑海里，他想知道在房间里他的影子的最大长度。

思路

首先不考虑照在墙上，用相似三角形可以手推出 y=x×hH−hy=x\times \frac{h}{H-h}。

如果照在墙上，也可以再弄一个相似推出 y=D−x+H−D×(H−h)xy=D-x+H-\frac{D\times(H-h)}{x}。

其中，D−xD-x 代表在地上的影子，H−D×(H−h)xH-\frac{D\times(H-h)}{x} 在墙上的影子。

易发现存在单谷性，可以用三分。

Code

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
#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define N
//#define M
//#define mo
int n, m, i, j, k, t; 
double H, h, D, l, r, lmid, rmid; 

double check(double x)
{
	if(x+x*h/(H-h)<=D) return x*h/(H-h); 
	return D-x+H-(H-h)*D/x; 
}

signed main()
{
//	freopen("tiaoshi.in","r",stdin);
//	freopen("tiaoshi.out","w",stdout);
	t=read(); 
	while(t--)
	{
		scanf("%lf%lf%lf", &H, &h, &D); 
		l=0; r=D; 
		while(r-l>1e-11)
		{
			lmid=l+(r-l)/3; 
			rmid=r-(r-l)/3; 
			if(check(lmid)>check(rmid))  r=rmid; 
			else l=lmid;
		}
		printf("%.3lf\n",  check(l)); 
	}
	return 0;
}

例题7：【P2571 [SCOI2010]传送带】

题目链接

题目

在一个 22 维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段 AB\text{AB} 和线段 CD\text{CD}。lxhgww 在 AB\text{AB} 上的移动速度为 PP，在 CD\text{CD} 上的移动速度为 QQ，在平面上的移动速度 RR。现在 lxhgww 想从 A\text A 点走到 D\text D 点，他想知道最少需要走多长时间。

思路

三分套三分。

现在AB上三分一个点，再在CD上三分一个点，易证符合单调性。

求距离需要用到一些数学知识。

Code

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
//#define M
//#define mo
//#define N
int n, m, i, j, k; 
double ax, ay, bx, by, cx, cy, dx, dy, p, q, r; 

double pingfa(double x)
{
	return x*x; 
}

double go(double lx, double ly, double rx, double ry, double speed)
{
	double s=sqrt(pingfa(rx-lx)+pingfa(ry-ly)); 
	return s/speed; 
}

double second_three_mid(double lstlx, double lstly)
{
	double lx, ly, rx, ry, tx, ty, nlx, nly, nrx, nry; 
	double lans, rans; 
	lx=cx; ly=cy; rx=dx; ry=dy; 
	while(abs(rx-lx)>1e-12||abs(ry-ly)>1e-12) 
	{
		
		tx=(rx-lx)/3; ty=(ry-ly)/3; 
		nlx=lx+tx; nly=ly+ty; 
		nrx=rx-tx; nry=ry-ty; 
		lans=go(lstlx, lstly, nlx, nly, q)+go(nlx, nly, dx, dy, r); 
		rans=go(lstlx, lstly, nrx, nry, q)+go(nrx, nry, dx, dy, r);
		// printf("> %lf %lf %lf %lf %lf %lf\n", lx, ly, rx, ry, lans, rans);  
		if(lans<rans) rx=nrx, ry=nry; 
		else lx=nlx, ly=nly; 
	}
	// printf("======= %lf %lf========", go(lstlx, lstly, lx, ly, q), go(lx, ly, dx, dy, r)); 
	return go(lstlx, lstly, lx, ly, q)+go(lx, ly, dx, dy, r); 
}

double first_three_mid()
{
	double lx, ly, rx, ry, tx, ty, nlx, nly, nrx, nry; 
	double lans, rans; 
	lx=ax; ly=ay; rx=bx; ry=by; 
	while(abs(rx-lx)>1e-12||abs(ry-ly)>1e-12)
	{
		// printf("> %lf %lf %lf %lf\n", lx, ly, rx, ry); 
		tx=(rx-lx)/3; ty=(ry-ly)/3; 
		nlx=lx+tx; nly=ly+ty; 
		nrx=rx-tx; nry=ry-ty; 
		lans=go(ax, ay, nlx, nly, p)+second_three_mid(nlx, nly); 
		rans=go(ax, ay, nrx, nry, p)+second_three_mid(nrx, nry); 
		// printf("\n%lf %lf %lf %lf %lf\n", nlx, nly, go(ax, ay, nlx, nly, p), second_three_mid(nlx, nly), lans); 
		// printf("\n%lf %lf %lf %lf %lf\n", nrx, nry, go(ax, ay, nrx, nry, p), second_three_mid(nrx, nry), rans); 
		if(lans<rans) rx=nrx, ry=nry/*, printf("right\n")*/; 
		else lx=nlx, ly=nly; 
	}
	// printf("--- %lf %lf\n", go(ax, ay, lx, ly, p), second_three_mid(lx, ly)); 
	return go(ax, ay, lx, ly, p)+second_three_mid(lx, ly); 
}

signed main()
{
//	freopen("tiaoshi.in", "r", stdin); 
//	freopen("tiaoshi.out", "w", stdout); 
	ax=double(read()); ay=double(read()); 
	bx=double(read()); by=double(read()); 
	cx=double(read()); cy=double(read()); 
	dx=double(read()); dy=double(read()); 
	if(ax==dx&&ay==dy) return printf("0.00"), 0; 
	p=double(read()); r=double(read()); q=double(read()); 
	printf("%.2lf", first_three_mid());  
	return 0; 
}