二分

解决范围

二分法可以用来解决这一系列具有单调性质的题，例如求单调函数的零点

其实在小学奥数中就用到了二分法

例如手动开根号，再比如猜数游戏

二分的具体过程就是先取一个中间值，判定一下正确答案在哪边，然后接着再二分，直到找到答案为止

二分法的本质是把求解问题转化成判定问题

优势

二分相对于暴力枚举来讲，判定次数会显著变少

具体来说，如果暴力枚举期望是O(N)次

那么二分只需要O(logN)次就可以得出答案

模板

//整数版

while(l<r)

{

	mid=(l+r)/2;

	if(check(mid)) r=mid;

	else l=mid+1;

}

while(l<r)

{

	mid=(l+r+1)/2;//注意+1

	if(check(mid)) l=mid;

	else r=mid-1;

}

//小数版

while(r-l>eps)

{

	mid=(l+r)/2;

	if(check(mid)>0) l=mid;

	else r=mid-eps;

}

//其中eps=1e-6或1e-8；依照题而定

例题

派

题目1

我的生日要到了！根据习俗，我需要将一些派分给大家。我有N个不同口味、不同大小的派。有F个朋友会来参加我的派对，每个人会拿到一块派（必须一个派的一块，不能由几个派的小块拼成；可以是一整个派）。

我的朋友们都特别小气，如果有人拿到更大的一块，就会开始抱怨。因此所有人拿到的派是同样大小的（但不需要是同样形状的），虽然这样有些派会被浪费，但总比搞砸整个派对好。当然，我也要给自己留一块，而这一块也要和其他人的同样大小。

请问我们每个人拿到的派最大是多少？每个派都是一个高为1，半径不等的圆柱体。

代码1

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<queue>

#include<vector>

#define N 100010

#define ll long long

#define dd double

using namespace std;

int n,f;

dd a[N];

const dd pie=3.1415926535;

bool check(dd mid)

{

	ll sum=0;

	for(int i=1;i<=n;i++)

	{

		sum+=a[i]/mid;

	}

	if(sum>=f) return 1;

	else return 0;

}

int main()

{

	cin>>n>>f;

	dd l=0,r=0;

	for(int i=1;i<=n;i++)

	{

		dd x;

		cin>>x;

		a[i]=x*x*pie*1;

		r=max(a[i],r);

	}

	dd eps=0.001;

	while(r-l>eps)

	{

		dd mid=(l+r)/2.0;

		if(check(mid)) l=mid;

		else r=mid-eps;

	}

	printf("%0.3lf",l);

	return 0;

}

题目2

把一个包含n个正整数的序列划分为m个连续的子序列(每个正整数恰好属于一个序列)。设第i个序列的各数之和为S(i)，你的任务是让所有S(i)的最大值尽量小。

例如序列1 2 3 2 5 4划分成3个序列的最优方案为1 2 3|2 5 |4，其中S(1)、S(2)、S(3)分别为6、7、4，最大值为7；如果划分成1 2|3 2|5 4，则最大值为9，不如刚才的好。

n<=10^{6，所有数之和不超过10}9。

代码2

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<queue>

#include<vector>

#define N 100010

#define ll long long

using namespace std;

ll n,k,a[N];

bool check(ll mid)

{

	int sum=0,j=1;

	for(int i=1;i<=n;i++)

	{

		sum+=a[i];

		if(a[i]>mid) return 0;

		if(sum>mid)

		{

			j++;

			sum=a[i];

		}

	}

	if(j>k) return 0;

	else return 1;

}

int main()

{

	scanf("%d%d",&n,&k);

	ll l,r=0;

	l=-100;

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&a[i]);

		l=max(l,a[i]);

		r+=a[i];

	}

	while(l<r)

	{

		ll mid=l+r>>1;

		if(check(mid)) r=mid;

		else l=mid+1;

	}

	cout<<l<<endl;

	return 0;

}

题目3

公园里有n个水塘，需要把这n个水塘中的水排干，水塘中的水在自然条件下1个单位的时间可以蒸发A升水。现在买了1台抽水机，使用抽水机可以让你用1个单位的时间使每个水塘除开自然蒸发的A升水外，还可抽B升水，但在1个单位的时间内只能对1个水塘使用。

要你求出排干所有水塘的最少时间（水塘中的水为0时为排干）。

代码3

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<queue>

#include<vector>

#define N 100010

#define ll long long

using namespace std;

ll n,a[N],A,B;

bool check(ll mid)

{

	int sum=0;

	int jian=mid*A;

	for(int i=1;i<=n;i++)

	{

		int ai=a[i]-jian;

		if(ai>0)

		{

			sum+=ai/B;

			if(ai%B!=0) sum++;

		}

	}

	if(sum>mid) return 0;

	else return 1;

} 

int main()

{

	cin>>n>>A>>B;

	ll l=0,r=0;

	for(int i=1;i<=n;i++)

	{

		cin>>a[i];

		r+=a[i];

	}

	while(l<r)

	{

		ll mid=l+r>>1;

		if(check(mid)) r=mid;

		else l=mid+1;

	}

	cout<<l<<endl;

	return 0;

}

/*

5 3 4

19 12 15 23 7

答案：5

*/

题目4

给出两个长度为n的正整数有序数组A和B, 在A和B中各任取一个, 可以得到n×n个积. 求第n小的元素。

n<=100000

思路4

判定有多少乘积小于这个答案就可以继续二分

但是怎么判定呢？

由于两个数组都是有序的，所以A数组中可行的乘积对应B数组一定是从头开始的一段序列，并且范围逐渐变小

这样我们O(N)扫一遍，用一个指针维护一下B数组合法位置就可以了

代码4

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<queue>

#include<vector>

#define N 100010

#define ll long long

#define dd double

using namespace std;

ll n/*,m*/,a[N],b[N];

bool check(ll mid)

{

	int sum=0,j=1,i=n;

	while(i>=1&&j<=n)

	{

		if(a[i]*b[j]<mid)

		{

			sum+=i;

			j++;

		}

		else i--;

	}

	//cout<<sum+1<<endl;

	sum++;

	if(sum<=n) return 1;

	else return 0;

}

int main()

{

	cin>>n;

	ll l=0,r=0;

	ll max1;

	for(int i=1;i<=n;i++) cin>>a[i],r=max(r,a[i]);

	for(int i=1;i<=n;i++) cin>>b[i],max1=max(max1,b[i]);

	r=max1*r;

	//cin>>m;check(m);

	while(l<r)

	{

		ll mid=l+r+1>>1;

		if(check(mid)) l=mid;

		else r=mid-1;

	}

	cout<<l<<endl;

	return 0;

}

/*

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<queue>

#include<vector>

#define N 100010

#define ll long long

#define dd double

using namespace std;

ll n,a[N],b[N],c[N],tail;

int main()

{

	cin>>n;

	for(int i=1;i<=n;i++) cin>>a[i];

	for(int i=1;i<=n;i++) cin>>b[i];

	for(int i=1;i<=n;i++)

	  for(int j=1;j<=n;j++)

	    c[++tail]=a[i]*b[j];

	sort(c+1,c+tail+1);

	cout<<c[n];

}

*/

/*

5

12 23 112 231 345

23 123 423 2390 8492

答案：2829

5

1 2 3 4 5

2 3 4 5 6

答案：5

*/

题目5

一年一度的“跳石头”比赛又要开始了！

这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。

为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。

求最短跳跃距离的最大值

N,M<=50000

代码5

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<queue>

#include<map>

#include<vector>

#include<set>

#include<deque>

#define dd double

#define ll long long

#define N 10000100

using namespace std;

ll n,m,a[N];

ll l;

bool check(ll mid)

{

	int now=0;

	int sum=0;

	for(int i=1;i<=n+1;i++)

	{

		if(a[i]-a[now]<mid) sum++;

		else now=i;

	}

	//cout<<mid<<" "<<sum<<endl;

	if(sum<=m) return 1;

	else return 0;

}

int main()

{

	cin>>l>>n>>m;

	for(int i=1;i<=n;i++)

	{

		cin>>a[i];

	}

	a[n+1]=l;

	ll r=l;

	l=0;

	while(l<r)

	{

		ll mid=l+r+1>>1;

		if(check(mid)) l=mid;

		else r=mid-1;

	}

	cout<<l<<endl;

	return 0;

}

三分

与二分法类似，三分法可以用来解决具有单峰性质的题

三分的具体过程就是先取两个中间值，分别位于1/3和2/3处，根据单峰性判定一下正确答案在前2/3还是后2/3，然后接着再三分，直到找到答案或答案的近似值为止

二分法每次把答案范围缩小一半，三分法每次把答案范围变为原来的2/3，他们的时间复杂度都是O(log(n))的

题目1

在一个2维平面上有两条传送带，每一条传送带可以看成是一条线段。两条传送带分别为线段AB和线段CD。小y在AB上的移动速度为P，在CD上的移动速度为Q，在平面上的移动速度R。现在小y想从A点走到D点，他想知道最少需要走多长时间？

思路1

小y走的路径一定是三条线段组成的折线

如果把离开AB线段的点设为x，到达CD的点设为y，总时间设为z，那么z是关于x，y的二元函数

可以证明这个函数形如一个山丘，也就是说可以先三分x再三分y求出z的最值

代码1

详见https://www.cnblogs.com/TianMeng-hyl/p/12309214.html

巴特西

浅谈二分—— by hyl天梦

二分

解决范围

优势

模板

例题

派

题目1

代码1

题目2

代码2

题目3

代码3

题目4

思路4

代码4

题目5

代码5

三分

题目1

思路1

代码1

最新文章

热门文章