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

目录前言一、 二分算法1.1 二分答案1.1.1 木材加工1.1.2 砍树1.1.3 跳石头结语 云泽Q个人主页 专栏传送入口: 《C语言》《数据结构》《C》《Linux》《蓝桥杯系列》⛺️遇见安然遇见你不负代码不负卿~前言大家好啊我是云泽Q欢迎阅读我的文章一名热爱计算机技术的在校大学生喜欢在课余时间做一些计算机技术的总结性文章希望我的文章能为你解答困惑~一、 二分算法1.1 二分答案1.1.1 木材加工木材加工解法学习「二分答案」这个算法基本上都会把这道比较简单的题当成例题设要切成的长度为能切成的段数为C。根据题意我们可以发现如下性质可以利用该规律衍生到二分当x增大的时候c在减小。也就是最终要切成的长度越大能切的段数越少x当减小的时候c在增大。也就是最终要切成的长度越小能切的段数越多。可以在这个单调性的基础上稍微优化一下暴力解法可以从大到小枚举切割长度x当x在减小的过程中c在逐渐增大当第一次出现切割出来的段数7的时候第一次出现的那个x一定是最终结果在整个「解空间」里面设最终的结果是ret于是有当xret时c≥k。也就是「要切的长度」小于等于「最优长度」的时候最终切出来的段数「大于等于」k当xret时ck。也就是「要切的长度」大于「最优长度」的时候最终切出来的段数「小于」k在解空间中根据ret的位置可以将解集分成两部分具有「二段性」那么我们就可以「二分答案」。#includeiostreamusingnamespacestd;typedeflonglongLL;constintN1e510;LL a[N];LL n,k;LLcalc(LL x){LL cnt0;for(inti1;in;i){cnta[i]/x;}returncnt;}intmain(){cinnk;for(inti1;in;i)cina[i];//不管读入原木的最长长度了//接按题目给的数据范围给到最大1e8LL left0,right1e8;while(leftright){LL mid(leftright1)/2;if(calc(mid)k)leftmid;elserightmid-1;}coutleftendl;return0;}这段代码采用二分查找策略来求解最大切割长度 l时间复杂度如下二分查找次数查找区间为 [0,maxL​]maxL​ 为原木最大长度本题中为 108二分次数约为 log(108)≈27 次。单次验证时间每次二分需要调用 calc 函数遍历所有 n 根原木n≤105统计可切割的总段数时间复杂度为 O(n)。因此总时间复杂度为 O(n⋅logmaxL​)代入数据规模后约为 105×272.7×106 次操作完全在可接受的时间范围内。避免计算溢出在 calc 函数中统计总段数 cnt 时若切割长度 x 很小如 x1每根原木可切割出的段数为 Li​n 根原木的总段数可能达到 105×1081013。而 int 类型的最大值仅约 2.1×109远小于 1013若用 int 存储 cnt会导致整数溢出计算结果完全错误。因此cnt 必须用 long long 类型。变量范围匹配题目中 k 的范围是 1≤k≤108虽然 int 可以存储但在比较 calc(mid) k 时calc(mid) 返回的是 long long 类型为避免类型不匹配导致的隐式转换问题k 也应定义为 long long。原木长度 Li​ 的范围是 1≤Li​≤108单个 Li​ 可用 int 存储但在计算 Li​/x 并累加到 cnt 时为避免类型转换开销Li​ 也应定义为 long long。1.1.2 砍树砍树#includeiostreamusingnamespacestd;constintN1e610;typedeflonglongLL;LL a[N];LL n,m;LLcalc(LL x){LL ret0;for(inti1;in;i){if(a[i]x)reta[i]-x;}returnret;}intmain(){cinnm;for(inti1;in;i)cina[i];LL left0,right4e5;while(leftright){LL mid(leftright1)/2;if(calc(mid)m)leftmid;elserightmid-1;}coutleftendl;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时cM。也就是「每次跳的最短距离」小于等于「最优距离」时移走的石头块数「小于等于」M当xret时cM。也就是「每次跳的最短距离」大于「最优距离」时移走的石头块数「大于」M。在解空间中根据ret的位置可以将解集分成两部分具有「二段性」那么我们就可以「二分答案」。当我们每次二分一个最短距离x时如何算出移走的石头块数c定义前后两个指针ij遍历整个数组设i≤j每次j从i的位置开始向后移动;当第一次发现a[j]一a[i]≥x时说明[i1,j一1]之间的石头都可以移走;然后将i更新到j的位置继续重复上面两步。#includeiostreamusingnamespacestd;typedeflonglongLL;constintN5e410;LL l,n,m;LL a[N];// 当最短跳跃距离为 x 时移走的岩石数目LLcalc(LL x){LL ret0;for(inti0;in;i){intji1;while(jna[j]-a[i]x)j;retj-i-1;ij-1;}returnret;}intmain(){cinlnm;for(inti1;in;i)cina[i];a[n1]l;n;LL left1,rightl;while(leftright){LL mid(leftright1)/2;if(calc(mid)m)leftmid;elserightmid-1;}coutleftendl;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;i1到j-1共有j-i-1块岩石这些都要移走累加到ret。i j - 1;因为for循环会执行i所以把i设为j-1下一次循环i就变成j直接从新保留的j开始找下一个跳过已经移走的岩石。时间复杂度1. 二分查找部分我们在区间 [1, L] 中寻找最大的满足条件的跳跃距离 x其中 L≤109。二分查找的次数为 log​(109)≈30 次时间复杂度为 O(logL)。2. calc(x) 函数部分calc(x) 用于计算当最短跳跃距离至少为 x 时需要移走的岩石数量。代码中使用了双指针i 和 ji 代表当前所在的岩石位置j 从 i1 开始向后寻找第一个满足 a[j] - a[i] x 的岩石。由于 i 和 j 都是单向递增j 永远不会回退i 会被设置为 j-1整个数组只会被遍历一次。因此 calc(x) 的时间复杂度为 O(n)n 为岩石总数 1包含终点。3. 整体时间复杂度每次二分查找都会调用一次 calc(x)因此总时间复杂度为O(nlogL)​代入题目数据规模验证n≤5×104logL≈30总操作数约为 5×104×301.5×106完全在时间限制内不会超时。结语