c++算法之二分

发布时间:2024年01月13日

目录

二分法简介

解题步骤

整数二分

模板

例题

输入描述

输出描述

样例输入输出

浮点二分

模板

二分答案(最重要)

模板

例题 跳石头

题目描述

输入描述

输出描述

输入输出样例

例题 肖恩的苹果林

输入描述

输出描述

测试

例题 肖恩的乘法表


二分法简介

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

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

二分法本质也是枚举,但和暴力枚举不同,二分法利用数据结构的单调性减少了很多不必要的枚举,从而极大的提高了效率,一般可以将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;
}

文章来源:https://blog.csdn.net/weixin_63201442/article/details/135566428
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。