c++算法之二分

目录

二分法简介

解题步骤

整数二分

模板

例题

输入描述

输出描述

样例输入输出

解

浮点二分

模板

二分答案（最重要）

模板

例题 跳石头

题目描述

输入描述

输出描述

输入输出样例

解

例题 肖恩的苹果林

输入描述

输出描述

解

测试

例题 肖恩的乘法表

解

---

二分法简介

二分法是一种高效的查找方法，它通过将问题的搜索范围一分为二（两边具有明显的区别），迭代的缩小搜索范围，直到找到目标或确定目标不存在。

二分法使用于有序数据集合，并且每次迭代可以将搜索范围缩小一半。

二分法本质也是枚举，但和暴力枚举不同，二分法利用数据结构的单调性减少了很多不必要的枚举，从而极大的提高了效率，一般可以将O(n)的枚举优化到O(logn)

解题步骤

1.研究并发现数据结构(或答案变量)的单调性。

2.确定最大区间[l,r]，确保分界点一定在里面，具有一定细节：若以r作为答案，那么答案区间在[l+1,r],若以l为答案，那么答案区间在[l,r-1]

3.确定check函数，一般为传入mid（区间中某个下标），返回mid所属区域或返回一个值，当check函数较简单时可直接判断

4.计算中点mid = （1+r）/2，用check判断该移动l或r指针，具体移动哪个需要根据单调性以及要求的答案来判断。

5.返回l或r，根据题意判断

整数二分

整数二分就是在一个已有的有序数组上，进行二分查找，一般为找出某个值的位置，或者是找出分界点。

这个数组肯定是开的下的，其数组大小一般在1e6以内。

模板

//找到升序数组a中的x第一次出现的位置
int l = 0,r = 1e9;
//注意这里的判断，这样可以保证l，r最终一定收敛到分界点
while(l+1!=r)//l r相邻退出
{
    int mid = (l+r)/2;
    //如果a为升序，说明mid偏大了，需要减小mid，就只能将r变小，即r = mid
    if(a[mid]>=x)r = mid;
    else l = mid;
}
cout<<r<<endl;

例题

给定一个数组，其采用如下代码定义

int data[200];
for(i = 0;i < 200;i++)data[i]=4*i+6;

先给定某个数（在data数组中），请你求出它在数组中的位置。

输入描述

输入一个待查找的整数（该整数一定在数组data中）

输出描述

输出该整数在数组中的指标

样例输入输出

输入262 输出64

解

#include<iostream>
using namespace std;
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int data[200];
	for (int i = 0; i < 200; i++)
	{
		data[i] = 4 * i + 6;
	}
	int x; cin >> x;
	int l = -1, r = 199;//为什么是-1 因为最后要返回r r的范围是l+1到r 即0到199
	while (l + 1 != r)
	{
		int mid = (l + r) >> 1;//二进制右移一位 相当于÷2
		if (data[mid] >= x)r = mid;
		else l = mid;
	}
	cout << r << endl;
	system("pause");
	return 0;
}

浮点二分

浮点二分不再是在有序数组上做二分查找，而是在某个实数范围内进行查找，因为实数域本身就是单调的，所以也满足单调性，和整数二分主要区别就在于使用的变量类型、退出的判断条件不同。

模板

//计算单调函数f(x)的零点
double l = 0,r = 1e9,eps = 1e-6;
//注意这里的判断条件，这样可以保证l，r最终一定收敛到分界点
while(r-l>=eps)//eps是一个极小量，设置为1e-6较合适
{
    double mid = (l+r)/2;
    //f(x)单调递增，f(mid)>=0,说明mid偏大了，需要减小mid，就只能将r变小，即r = mid
    if(f(mid))>=0)r = mid;
    else l = mid;
}
//最后返回l，r差别不大
cour<< r <<endl;

二分答案（最重要）

二分答案是二分法中最常见也最重要的题型，考察的比较灵活，需要选手从题目中发现某个单调的函数，然后对其二分

常见的模型是：

二分框架（时间复杂度O(logm)+check函数(时间复杂度O(n))

一般情况下，我们会将答案进行二分，然后再枚举出某个可能解后判断其是否可以更优或者是否合法，从而不断逼近最优解

二分答案的题的特征：如果已知某个答案，很容易判断其是否合法或更优。某些贪心问题可能可以转化成二分答案问题

模板

bool check(int mid)
{
    bool res = true;
    //do sth to check the authority of mid
    return res;
}
int main()
{
    int l = 0,r = 1e9;
    while(l+1!=r)
    {
        int mid = (l+r)/2;
        //具体写法需要根据题意修改
        if(check(mid))l = mid;
        else r= mid;
}
cout<<l<<endl;

例题 跳石头

题目描述

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

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

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

输入描述

输入文件第一行包含三个整数 L，N，M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。

接下来 N 行，每行一个整数，第 i 行的整数 （0<Di<L）表示第i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置。

其中，0≤5×104，1≤1090≤M≤N≤5×104，1≤L≤109

输出描述

输出只包含一个整数，即最短跳跃距离的最大值。

输入输出样例

? ? 输入
? ? 25 5 2
? ? 2
? ? 11
? ? 14
? ? 17
? ? 21?

? ? 输出
? ? 4

解

#include<iostream>
using namespace std;
using ll = long long;
const int N = 5e4 + 9;
int a[N], L, n, m;

int check(int mid)
{
	//当最远跳跃距离为mid的情况下，至少需要搬走多少块石头
	int res = 0,lst=0;
	for (int i = 1,lst = 0; i <= n; i++)//lst表示上一块石头的位置
	{
		if (a[i] - a[lst] < mid)
		{
			res++;
			continue;
		}
		lst = i;

	}
	if (L - a[lst] < mid)
	{
		return m + 1;//这种情况不行，因为最后一块石头不能被搬走
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> L >> n >> m;
	for (int i = 1; i <= n; ++i)cin >> a[i];

	ll l = 0, r = 1e9 + 5;
	while (l + 1 != r)
	{
		ll mid = (l + r) / 2;
		if (check(mid) <= m)l = mid;
		else r = mid;

	}
	cout << l << endl;

	return 0;
}

例题 肖恩的苹果林

肖恩有一大片农田，农田中有 N 个可以种植苹果树的位置。这些位置都分布在一条直线上，坐标是 x1,x2,..,xN 。肖恩得到了 M 个树苗，需要种到农田中的对应位置.
我们都知道两棵苹果树种的距离如果太近的话会互相争抢养分，导致两棵苹果树都会营养不良。所以肖恩认为相邻两棵苹果树之间的最近距离越大越好，那么请你帮肖恩算算最大的最近距离是多少?

输入描述

第一行输入两个整数N和M，两个数的意义和题面中描述相同
第二行输入N个数字，第i个数字 xi表示第i个可以种植苹果树的位置

输出描述

输出一个数字表示最大的最近距离

解

#include<iostream>
#include<algorithm>
using namespace std;
using ll = long long;
const int N = 5e4 + 9;
int x[N], n, m;

int check(int mid)
{
	
	int res = 0,lst=0;
	for (int i = 1, lst = 0; i <= n; i++)
	{
		if (lst && x[i] - x[lst] < mid)continue;
		res++, lst = i;
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >>n >> m;
	for (int i = 1; i <= n; ++i)cin >> x[i];
	sort(x + 1, x + 1 + n);

	ll l = 0, r = 1e9 + 5;
	while (l + 1 != r)
	{
		ll mid = (l + r) / 2;
		if (check(mid) >= m)l = mid;//最多能种多少树 大于m 说明间隙小了 要增大
		else r = mid;

	}
	cout << l << endl;

	return 0;
}

测试

5 3
1 3 4 8 9
3

例题 肖恩的乘法表

解

#include<iostream>
#include<algorithm>
#include<windows.h>
using namespace std;
using ll = long long;
const int N = 5e4 + 9;
ll n, m, k;

ll check(ll mid)
{
	
	ll res = 0;
	for (int i = 1; i <= n; i++)//每一行多少个数字<mid
	{
		res += min(m, mid / i);
	}
	return res;
}
int main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >>n >> m>>k;

	ll l = 0, r = 1e14;
	while (l + 1 != r)
	{
		ll mid = (l + r) >> 1;
		if (check(mid) >= k)r = mid;
		else l = mid;

	}
	cout << r << endl;

	return 0;
}