蓝桥杯算法精讲：二分算法之二分答案深度剖析

前言

大家好啊，我是云泽Q，欢迎阅读我的文章，一名热爱计算机技术的在校大学生，喜欢在课余时间做一些计算机技术的总结性文章，希望我的文章能为你解答困惑~

一、 二分算法

1.1 二分答案

1.1.1 木材加工

木材加工

解法
学习「二分答案」这个算法，基本上都会把这道比较简单的题当成例题

设要切成的长度为，能切成的段数为C。根据题意，我们可以发现如下性质，可以利用该规律衍生到二分：

• 当x增大的时候，c在减小。也就是最终要切成的长度越大，能切的段数越少；
• x当减小的时候，c在增大。也就是最终要切成的长度越小，能切的段数越多。

可以在这个单调性的基础上，稍微优化一下暴力解法，可以从大到小枚举切割长度x，当x在减小的过程中，c在逐渐增大，当第一次出现切割出来的段数>=7的时候，第一次出现的那个x一定是最终结果

在整个「解空间」里面，设最终的结果是ret，于是有：

• 当x<ret时，c≥k。也就是「要切的长度」小于等于「最优长度」的时候，最终切出来的段数「大于等于」k；
• 当x>ret时，c<k。也就是「要切的长度」大于「最优长度」的时候，最终切出来的段数「小于」k；

在解空间中，根据ret的位置，可以将解集分成两部分，具有「二段性」，那么我们就可以「二分答案」。

#include<iostream>usingnamespacestd;typedeflonglongLL;constintN=1e5+10;LL a[N];LL n,k;LLcalc(LL x){LL cnt=0;for(inti=1;i<=n;i++){cnt+=a[i]/x;}returncnt;}intmain(){cin>>n>>k;for(inti=1;i<=n;i++)cin>>a[i];//不管读入原木的最长长度了，//接按题目给的数据范围给到最大1e8LL left=0,right=1e8;while(left<right){LL mid=(left+right+1)/2;if(calc(mid)>=k)left=mid;elseright=mid-1;}cout<<left<<endl;return0;}

这段代码采用二分查找策略来求解最大切割长度 l，时间复杂度如下：

• 二分查找次数：查找区间为 [0,maxL​]（maxL​ 为原木最大长度，本题中为 108），二分次数约为 log(108)≈27 次。
• 单次验证时间：每次二分需要调用 calc 函数，遍历所有 n 根原木（n≤105），统计可切割的总段数，时间复杂度为 O(n)。

因此，总时间复杂度为 O(n⋅logmaxL​)，代入数据规模后约为 105×27=2.7×106 次操作，完全在可接受的时间范围内。

1. 避免计算溢出：在 calc 函数中，统计总段数 cnt 时，若切割长度 x 很小（如 x=1），每根原木可切割出的段数为 Li​，n 根原木的总段数可能达到 10⁵×10⁸=10¹³。而 int 类型的最大值仅约 2.1×10⁹，远小于 10¹³，若用 int 存储 cnt，会导致整数溢出，计算结果完全错误。因此，cnt 必须用 long long 类型。

2. 变量范围匹配
   题目中 k 的范围是 1≤k≤10⁸，虽然 int 可以存储，但在比较 calc(mid) >= k 时，calc(mid) 返回的是 long long 类型，为避免类型不匹配导致的隐式转换问题，k 也应定义为 long long。
   原木长度 Li​ 的范围是 1≤Li​≤10⁸，单个 Li​ 可用 int 存储，但在计算 Li​/x 并累加到 cnt 时，为避免类型转换开销，Li​ 也应定义为 long long。

1.1.2 砍树

砍树

#include<iostream>usingnamespacestd;constintN=1e6+10;typedeflonglongLL;LL a[N];LL n,m;LLcalc(LL x){LL ret=0;for(inti=1;i<=n;i++){if(a[i]>x)ret+=a[i]-x;}returnret;}intmain(){cin>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];LL left=0,right=4e5;while(left<right){LL mid=(left+right+1)/2;if(calc(mid)>=m)left=mid;elseright=mid-1;}cout<<left<<endl;return0;}

这道题时间复杂度和思路基本和上道题完全一样

1.1.3 跳石头

跳石头


这道题是最大化最小值的经典二分问题：

• 我们二分一个「最短跳跃距离」x，想知道：如果要求所有保留岩石的相邻跳跃距离都 ≥ x，最少需要移走多少块岩石？
• calc(x) 就是用来计算这个「最少移走数」的函数。
  如果 calc(x) ≤ M：说明x是可行的（移走的石头不超过限制），可以尝试更大的x；
  如果 calc(x) > M：说明x太大了，需要缩小。

解法
设每次跳的最短距离是x，移走的石头块数为c。根据题意，我们可以发现如下性质：

• 当x增大的时候，c也在增大;
• 当x减小的时候，c也在减小。

那么在整个「解空间」里面，设最终的结果是ret，于是有：

• 当x≤ret时，c<=M。也就是「每次跳的最短距离」小于等于「最优距离」时，移走的石头块数「小于等于」M；
• 当x>ret时，c>M。也就是「每次跳的最短距离」大于「最优距离」时，移走的石头块数「大于」M。

在解空间中，根据ret的位置，可以将解集分成两部分，具有「二段性」，那么我们就可以「二分答案」。

当我们每次二分一个最短距离x时，如何算出移走的石头块数c？

• 定义前后两个指针i，j遍历整个数组，设i≤j，每次j从i的位置开始向后移动;
• 当第一次发现a[j]一a[i]≥x时，说明[i+1,j一1]之间的石头都可以移走;
• 然后将i更新到j的位置，继续重复上面两步。

#include<iostream>usingnamespacestd;typedeflonglongLL;constintN=5e4+10;LL l,n,m;LL a[N];// 当最短跳跃距离为 x 时，移走的岩石数目LLcalc(LL x){LL ret=0;for(inti=0;i<=n;i++){intj=i+1;while(j<=n&&a[j]-a[i]<x)j++;ret+=j-i-1;i=j-1;}returnret;}intmain(){cin>>l>>n>>m;for(inti=1;i<=n;i++)cin>>a[i];a[n+1]=l;n++;LL left=1,right=l;while(left<right){LL mid=(left+right+1)/2;if(calc(mid)<=m)left=mid;elseright=mid-1;}cout<<left<<endl;return0;}

补充一下这里calc内部的一些细节问题：
1. 核心贪心逻辑
要让「移走的岩石最少」，必须遵循一个原则：
从当前保留的岩石i出发，找第一个满足「距离≥x」的岩石j，把i和j之间的所有岩石都移走。这样做能保证：中间移走的岩石数量最少，总移走数全局最小。

3. 关键代码解释

• while(j <= n && a[j] - a[i] < x) j++;从i的下一个岩石开始，往后找，直到找到第一个「距离i≥x」的岩石j。（i和j之间的岩石，距离i都 < x，必须移走，否则违反「最短跳跃≥x」的要求）
• ret += j - i - 1;i+1到j-1共有j-i-1块岩石，这些都要移走，累加到ret。
• i = j - 1;因为for循环会执行i++，所以把i设为j-1，下一次循环i就变成j，直接从新保留的j开始找下一个，跳过已经移走的岩石。

时间复杂度
1. 二分查找部分
我们在区间 [1, L] 中寻找最大的满足条件的跳跃距离 x，其中 L≤10⁹。
二分查找的次数为 log​(10⁹)≈30 次，时间复杂度为 O(logL)。

2. calc(x) 函数部分
calc(x) 用于计算：当最短跳跃距离至少为 x 时，需要移走的岩石数量。
代码中使用了双指针（i 和 j）：
i 代表当前所在的岩石位置，j 从 i+1 开始向后寻找第一个满足 a[j] - a[i] >= x 的岩石。
由于 i 和 j 都是单向递增（j 永远不会回退，i 会被设置为 j-1），整个数组只会被遍历一次。

因此 calc(x) 的时间复杂度为 O(n)（n 为岩石总数 + 1，包含终点）。

3. 整体时间复杂度
每次二分查找都会调用一次 calc(x)，因此总时间复杂度为：O(nlogL)​
代入题目数据规模验证：

n≤5×10⁴，logL≈30
总操作数约为 5×10⁴×30=1.5×10⁶，完全在时间限制内，不会超时。

结语