二分答案算法

目录二分答案题目一——P2440 木材加工 - 洛谷题目二——P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷题目三——P2678 [NOIP 2015 提高组] 跳石头 - 洛谷题目四—— P1843 奶牛晒衣服 - 洛谷题目五——P3853 [TJOI2007] 路标设置 - 洛谷题目六——P1182 数列分段 Section II - 洛谷题目七——P5119 [USACO18DEC] Convention S - 洛谷二分答案准确来说应该叫做「二分答案 判断」。二分答案可以处理大部分「最大值最小」以及「最小值最大」的问题。如果「解空间」在从大到小的变化过程中「判断」答案的结果出现「二段性」此时我们就可以「二分」这个「解空间」通过「判断」找出最优解。刚接触的时候可能觉得这个「算法原理」很抽象。没关系7 道题的练习过后你会发现这个「二分答案」的原理其实很容易理解重点是如何去「判断」答案的可行性。题目一——P2440 木材加工 - 洛谷学习「⼆分答案」这个算法基本上都会把这道⽐较简单的题当成例题~设要切成的长度为x在长度为x的时候能切成的段数为c。根据题意我们可以发现如下性质当x增大的时候c在减小。也就是最终要切成的长度越大能切的段数越少当x减小的时候c在增大。也就是最终要切成的长度越小能切的段数越多。那么在整个「解空间」里面设最终的切成的长度结果是retxret 时能切出至少 k 段可行xret时长度更短能切出的段数更多也可行xret 时长度更长能切出的段数变少不可行。于是我们采用的就是xret和xret的分法而不是说xret和xret的分法当x ≤ ret时c ≥ k。也就是「要切的长度」小于等于「最优长度」的时候最终切出来的段数「大于等于」k当x ret时c k。也就是「要切的长度」大于「最优长度」的时候最终切出来的段数「小于」k。在解空间中根据x的位置可以将解集分成两部分具有「二段性」那么我们就可以「二分答案」。现在这个我们已经知道这个ret就是k但是我们需要求解的是c啊注意不是x哦当我们每次二分一个切成的长度x的时候如何算出能切的段数c很简单遍历整个数组针对每根原木能切成的段数就是a[i] / x。#includeiostream #includevector using namespace std; int n,k; vectorintnums; long long call(long long x) { long long sum0; for(autot:nums) { sumt/x; } return sum; } int main() { cinnk; int tmp; for(int i0;in;i) { cintmp; nums.push_back(tmp); } long long left0,right1e810; while(leftright) { long long midleft(right-left1)/2; if(call(mid)k) { leftmid; } else { rightmid-1; } } coutleft; }特别注意我们不能简单的去套用这个二分查找算法的求解左右端点的这个模板。它的判断条件是注意我们本质是寻找符合条件的x而由于当x ≤ ret时c ≥ k我们只看x的分布我们就知道是寻找区间右端点当满足 calc(mid) k时也就是对应我们上面说的当当x ≤ ret时c ≥ k也就是说现在xk我们需要增大x但是我们是寻找区间右端点所以此时就是leftmid相当于我们已经知道要切几份根据这个求最长的切割长度。题目二——P1873 [COCI 2011/2012 #5] EKO / 砍树 - 洛谷设伐木机的高度为 H能得到的木材为 C。根据题意我们可以发现如下性质当 H 增大的时候C 在减小当 H 减小时C 在增大。那么在整个「解空间」里面设最终的结果是 ret于是有当 H ≤ ret 时C ≥ M。也就是「伐木机的高度」大于等于「最优高度」时能得到的木材「小于等于」M当 H ret 时C M。也就是「伐木机的高度」小于「最优高度」时能得到的木材「大于」M。在解空间中根据 ret 的位置可以将解集分成两部分具有「二段性」那么我们就可以「二分答案」。当我们每次二分一个伐木机的高度 H 的时候如何算出得到的木材 C很简单遍历整个数组针对每一根木头能切成的木材就是 a[i] − H。#include iostream using namespace std; typedef long long LL; const LL N 1e610; LL n, m; LL a[N]; // 当伐木机的高度为 x 时所能获得的木材量 LL calc(LL x) { LL ret 0; for (int i 1; i n; i) { if (a[i] x) ret a[i] - x; } return ret; } int main() { cin n m; for (int i 1; i n; i) cin a[i]; LL left0,right4e5;//注意这个范围是H的范围 while(leftright) { LL midleft(right-left1)/2;//注意是寻找右端点注意我们是求解的是H的 if(calc(mid)m)//千万别被迷惑了这个其实是对应的是midH的情况 { leftmid;//注意是H啊 } else { rightmid-1; } } coutleft; return 0; }注意我们本质是寻找符合条件的H而由于当 H ≤ ret 时C ≥ M我们只看H的情况我们就知道是寻找区间右端点当满足 calc(mid) m时也就是对应我们上面说的当当当 H ≤ ret 时C ≥ M也就是说现在H ≤ ret我们需要增大H但是我们是寻找区间右端点所以此时就是leftmid题目三——P2678 [NOIP 2015 提高组] 跳石头 - 洛谷设每次跳的最短距离是 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 using namespace std; typedef long long LL; const int N 5e4 10; LL l, n, m; LL a[N]; // 当最短跳跃距离为 x 时移除的石头数 LL calc(LL x) { LL ret 0; for (int i 0; i n; i) { int j i 1; while (j n a[j] - a[i] x) j; ret j - i - 1; i j - 1; } return ret; } int main() { cin l n m; for (int i 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; else right mid - 1; } cout left endl; return 0; }注意我们本质是寻找符合条件的x而由于当 x ≤ ret 时c ≤ M我们只看x的情况我们就知道是寻找区间右端点当满足 calc(mid) m时也就是对应我们上面说的当当x ≤ ret 时c ≤ M也就是说现在x ≤ ret我们需要增大x但是我们是寻找区间右端点所以此时就是leftmid题目四—— P1843 奶牛晒衣服 - 洛谷根据题意我们可以发现以下性质经过的时间如果是 x 的话烘干机的「使用次数」最多也是 x。当 x 在「增大」的时候能弄干的衣服在「增多」。当 x 在「减小」的时候能弄干的衣服也在「减少」。在整个「解空间」里面设弄干所有衣服的最少时间是 ret。于是有当 x≥ret 时我们「能弄干」所有衣服。当 xret 时我们「不能弄干」所有衣服。因此在解空间中根据 ret 的位置可以将解集分成两部分具有「二段性」。那么我们就可以「二分答案」。这不就是寻找区间左端点吗接下来的重点是给定一个时间 x判断「是否能把所有的衣服全部弄干」。当时间为 x 时所有衣服能够自然蒸发 a⋅x 的湿度于是如果 w[i]≤a⋅x让它自然蒸发如果 w[i]a⋅x需要用烘干机烘干。对于需要烘干的衣服其剩余湿度为 tw[i]−a⋅x烘干次数为 t / b (t % b 0 ? 0 : 1) 。向上取整。我们可以遍历所有的衣服计算烘干机的「使用次数」如果烘干机使用次数「大于」给定的时间 x说明不能全部弄干如果烘干机使用次数「小于等于」给定的时间 x说明能全部弄干。通过二分查找我们可以找到最小的 ret使得所有衣服都能在 ret 时间内被弄干。#includebits/stdc.h using namespace std; typedef long long LL; const int N5e510; LL n,a,b; LL w[N]; bool check(LL x) { int cnt0; for(int i1;in;i) { if(w[i]x*a) { continue; } else { int tw[i]-x*a; cntt/b(t%b0?0:1); } } return cntx;//正常情况下cnt是小于x次的 } int main() { cinnab; for(int i1;in;i) { cinw[i]; } LL left1,right5e5;//注意这里是时间的取值范围 while(leftright) { LL midleft(right-left)/2; if(check(mid)false)//说明时间太短了才会导致烘干机使用次数变多 { leftmid1; } else { rightmid; } } coutleftendl; }注意我们本质是寻找符合条件的x而由于当 x≥ret 时我们「能弄干」所有衣服我们只看x的情况我们就知道是寻找区间左端点当满足 check(mid)false时也就是对应我们上面说的当 xret 时我们「不能弄干」所有衣服也就是说现在x ret我们需要增大x但是我们是寻找区间左端点所以此时就是leftmid1题目五——P3853 [TJOI2007] 路标设置 - 洛谷根据题意我们可以发现以下性质空旷指数是 x 最多可增设的路标数量为K。当 x 在「增大」的时候最多能增设的路标在「减少」。当 x 在「减小」的时候最多能增设的路标在「增加」。在整个「解空间」里面设最小空旷指数是 ret。于是有当 x≥ret 时最多能增设的路标K。当 xret 时最多能增设的路标K。因此在解空间中根据 ret 的位置可以将解集分成两部分具有「二段性」。那么我们就可以「二分答案」。这不就是找区间左端点吗那接下来的问题就是给定一个空旷指数x我们怎么计算出此时的最多能增设的路标呢da[i]−a[i−1]需要的路标数量是d/x.如果 d 能被 x 整除即 d%x0此时d/x1会重复计数我们需要将这个1去掉。#include iostream using namespace std; const int N 1e5 10; int len, n, k; int a[N]; bool check(int x) { int cnt 0; for (int i 2; i n; i) { int d a[i] - a[i - 1]; cnt d / x; if (d % x 0) cnt--;//注意d刚好等于x的时候会重复计数 } return cnt; } int main() { cin len n k; for (int i 1; i n; i) cin a[i]; int l 1, r len; while (l r) { int mid (l r) / 2; if (check(mid) k) r mid; else l mid 1; } cout l endl; return 0; }注意我们本质是寻找符合条件的x而由于当 x≥ret 时最多能增设的路标K我们只看x的情况我们就知道是寻找区间左端点当满足check(mid) k时也就是对应我们上面说的当 x≥ret 时最多能增设的路标K也就是说现在x≥ret我们需要减小x但是我们是寻找区间左端点所以此时就是rightmid题目六——P1182 数列分段 Section II - 洛谷根据题意我们可以发现以下性质当分的段数越多的时候最⼤的和越⼩当分的段数越少的时候最⼤的和越⼤。而在本题中我们知道的是分的段数M;我们就得使用不断修改每段和的最大值来逼近这个段数M。在整个「解空间」里面设每段和的最大值是 x而当分M段时每段和的最大值ret。于是有当每段和的最大值x≥ret 时分的段数的最小值M。当每段和的最大值xret 时分的段数的最小值M。因此在解空间中根据 ret 的位置可以将解集分成两部分具有「二段性」。那么我们就可以「二分答案」。注意我们找的是每段和的最大值所以本质就是寻找区间左端点那么问题变成了当我给你一个每段最大和我怎么计算出当前最少能分几段数呢很简单。从前往后累加只要和⼩于x就⼀直加直到和超过x之前的为⼀段然后从该位置继续累加。我们要注意这个每段和的最大值的取值范围是【单个元素里面的最大值所有元素的和】#includebits/stdc.h using namespace std; const int N1e510; long long nums[N]; int n,m; int call(int x) { int sum0,cnt0; for(int i1;in;i) { sumnums[i]; if(sumx) { cnt; sumnums[i]; } } return cnt1; } int main() { cinnm; long long left0,right0; for(int i1;in;i) { cinnums[i]; leftmax(left,nums[i]); rightnums[i]; } while(leftright) { int midleft(right-left)/2;//注意是寻找区间左端点 if(call(mid)m) { rightmid; } else { leftmid1; } } coutleftendl; }题目七——P5119 [USACO18DEC] Convention S - 洛谷⼆段性当等待时间增⻓的时候所⽤的⻋辆在减少当等待时间减少的时候所⽤的⻋辆在增加。#include iostream #include algorithm using namespace std; const int N 1e5 10; int n, m, c; int a[N]; int calc(int x) { int cnt 0; int l 1, r 1; while (r n) { while (r n a[r] - a[l] x r - l 1 c) r; cnt; l r; } return cnt; } int main() { cin n m c; for (int i 1; i n; i) cin a[i]; sort(a 1, a 1 n); int l 0, r a[n] - a[1]; while (l r) { int mid (l r) / 2; if (calc(mid) m) r mid; else l mid 1; } cout l endl; return 0; }