算法详解——二分

it2022-05-07  0

二分是一类比较常见、相对基础的算法,其代码往往是比较好写的,并且格式也比较固定,同时二分也是一类出错率比较高的算法,在你写完一份二分的代码放入测评机时,往往会发现你二分出的答案与正确答案比较接近,这都是正常现象,这也是二分比较难的地方——设定边界。那么为了防止大家犯这种错误,我接下来将会对二分算法进行详细的解析。

 


 

二分算法

 

给定一个长度为n的单调递增序列a,要求我们在a中找到一个合法的ai,使得ai是a序列中>=x的数中最小的一个...

那么我们首先考虑,若存在一个合法的ai,那么i一定是ans或ans的后继,那我们不妨设L=1,R=n,然后定义一个mid=(L+R)>>1,当amid>=x时,我们考虑mid右边的数一定不会是ans,所以我们让R=mid;同理,当amid<x时,让L=mid+1(因为此时的L也不会是ans),这样我们就构造出了一个合法的二分方法,代码如下:

 

while(L < R) { int mid = (L + R)>>1; if(a[mid] >= x) R = mid; else L = mid + 1; } return a[L] //a[L]即为ans

 

我们可以发现,这种二分方法只会取到L的值,却不会取到R的值,那么这个结论有什么用呢?

我们现在改变题意,假设现在我们求的是a中满足ai<=x的最大值,如果我们继续用这种二分方法,你会发现,当发现amid正好与x相等时,L会变成mid+1,那么它就变成了ans的下一个数了,就不对了,也就是说,对于这种情况下,我们需要另一种二分方案:

 

while(L < R) { int mid = (L + R + 1)>>1; if(a[mid] <= x) L = mid; else R = mid - 1; } return a[L] //a[L]即为ans

 

在上面的代码中,对比发现,mid这时取的是(L+R+1)/ 2了, 我们考虑为什么这么做,那么我们可以发现,当R-L为奇时,它与(L+R)/ 2无异,当R-L为偶时,那么它取的是中间两个元素的后者,而第一种代码是选择前者,所以,我们这样取mid,就可以使amid与x相等时,ans取当前的mid值...

 

当然,关于二分的技巧还有很多,在这里我们先说明这两种,接下来是一些二分的例题:

 


 

T1 洛谷P2678

题目背景

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

题目描述

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

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

输入输出格式

输入格式:

 

第一行包含三个整数 L,N,ML,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。保证 1 且 ≥ ≥ 0。

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

 

输出格式:

 

一个整数,即最短跳跃距离的最大值。

 

♦题解

本题是一个经典二分答案题,注意边界,没什么难度,代码如下:

#include <cstdio> #include <cstring> int L,n,m; int d[50008]; inline int read() //快读 { char ch = getchar(); int x = 0,f = 1; while(ch<'0'||ch>'9'){if(ch == '-') f = -1; ch = getchar();} while(ch>='0'&&ch<='9'){x = x*10 + ch -'0'; ch = getchar();} return x*f; } inline bool check(int x) { int pre = 0; //上一个未被移除的石块的位置 int move = 0; //需要移除的石块个数 for(int i = 1;i <= n + 1;i ++) { int dis = d[i] - d[pre]; if(dis < x) move ++; else pre = i; } if(m >= move) return true; else return false; } int main() { L = read(); n = read(); m = read(); for(int i = 1;i <= n;i ++) scanf("%d",&d[i]); d[n + 1] = L; int l = 0,r = L; int mid; while(l < r) { mid = (l + r + 1)>>1; if(check(mid)) l = mid; else r = mid - 1; } printf("%d",l); return 0; }

 


 

T2 洛谷P1439

 

题目描述

给出1-n的两个排列P1和P2,求它们的最长公共子序列。

输入输出格式

输入格式:

 

第一行是一个数n,

接下来两行,每行为n个数,为自然数1-n的一个排列。

 

输出格式:

 

一个数,即最长公共子序列的长度

 

♦题解

本题是一道DP题,求的是最长公共子序列(最长不降子序列

对,本来是最长公共子序列,但看一眼n≤100000,显然n^2不可能,于是我们考虑nlogn的做法

我们可以发现,其中一个序列为单调递增时,这个问题就转化成了求一个序列的最长不降子序列,代码如下:

 

#include <cstdio> #include <cstring> #include <algorithm> const int maxn = 1e5 + 5; int n; int f[maxn],a[maxn],b[maxn],map[maxn]; int main() { scanf("%d",&n); for(int i = 1;i <= n;i ++) scanf("%d",&a[i]),map[a[i]] = i; for(int i = 1;i <= n;i ++) scanf("%d",&b[i]); std::sort(a + 1,a + n + 1); f[1] = map[b[1]]; int cnt = 1; for(int i = 2;i <= n;i ++) { if(f[cnt]<map[b[i]]) f[++cnt] = map[b[i]]; else { int l = 1,r = cnt; while(l < r) { int m = (l + r)>>1; if(f[m]>map[b[i]]) r = m; else l = m + 1; } f[l] = std::min(f[l],map[b[i]]); } } printf("%d",cnt); return 0; }

 

转载于:https://www.cnblogs.com/Ackers/p/9995982.html

相关资源:垃圾分类数据集及代码

最新回复(0)