目录

二分答案

题目一——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在增大。也就是最终要切成的长度越小，能切的段数越多。

那么在整个「解空间」里面，设最终的切成的长度结果是ret，

• x=ret 时：能切出至少 k 段，可行；

• x<ret时：长度更短，能切出的段数更多，也可行；

• x>ret 时：长度更长，能切出的段数变少，不可行。

于是我们采用的就是x<=ret和x>ret的分法，而不是说x>=ret和x<ret的分法：

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

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

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

现在这个我们已经知道这个ret就是k，但是我们需要求解的是c啊，注意不是x哦！！！

当我们每次二分一个切成的长度x的时候，如何算出能切的段数c？

• 很简单，遍历整个数组，针对每根原木，能切成的段数就是a[i] / x。

#include<iostream> #include<vector> using namespace std; int n,k; vector<int>nums; long long call(long long x) { long long sum=0; for(auto&t:nums) { sum+=t/x; } return sum; } int main() { cin>>n>>k; int tmp; for(int i=0;i<n;i++) { cin>>tmp; nums.push_back(tmp); } long long left=0,right=1e8+10; while(left<right) { long long mid=left+(right-left+1)/2; if(call(mid)>=k) { left=mid; } else { right=mid-1; } } cout<<left; }

特别注意：我们不能简单的去套用这个二分查找算法的求解左右端点的这个模板。！！！！它的判断条件是

• 注意我们本质是寻找符合条件的x，而由于当x ≤ ret时，c ≥ k，我们只看x的分布，我们就知道是寻找区间右端点
• 当满足 calc(mid) >= k时，也就是对应我们上面说的当当x ≤ ret时，c ≥ k，也就是说现在x<=k，我们需要增大x，但是我们是寻找区间右端点，所以此时就是left=mid

相当于我们已经知道要切几份，根据这个求最长的切割长度。

题目二——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 =1e6+10; 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 left=0,right=4e5;//注意这个范围是H的范围 while(left<right) { LL mid=left+(right-left+1)/2;//注意是寻找右端点（注意我们是求解的是H的） if(calc(mid)>=m)//千万别被迷惑了，这个其实是对应的是mid<=H的情况 { left=mid;//注意是H啊 } else { right=mid-1; } } cout<<left; return 0; }

• 注意我们本质是寻找符合条件的H，而由于当 H ≤ ret 时，C ≥ M，我们只看H的情况，我们就知道是寻找区间右端点
• 当满足 calc(mid) >= m时，也就是对应我们上面说的当当当 H ≤ ret 时，C ≥ M，也就是说现在H ≤ ret，我们需要增大H，但是我们是寻找区间右端点，所以此时就是left=mid

题目三——P2678 [NOIP 2015 提高组] 跳石头 - 洛谷

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

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

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

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

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

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

1. 定义前后两个指针 i,j 遍历整个数组，设 i ≤ j，每次 j 从 i 的位置开始向后移动；
2. 当第一次发现 a[j] - a[i] ≥ x 时，说明 [i + 1, j - 1] 之间的石头都可以移走；
3. 然后将 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，但是我们是寻找区间右端点，所以此时就是left=mid

题目四—— P1843 奶牛晒衣服 - 洛谷

根据题意，我们可以发现以下性质：

• 经过的时间如果是 x 的话，烘干机的「使用次数」最多也是 x。

• 当 x 在「增大」的时候，能弄干的衣服在「增多」。

• 当 x 在「减小」的时候，能弄干的衣服也在「减少」。

在整个「解空间」里面，设弄干所有衣服的最少时间是 ret。于是有：

• 当 x≥ret 时，我们「能弄干」所有衣服。

• 当 x<ret 时，我们「不能弄干」所有衣服。

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

这不就是寻找区间左端点吗！！

接下来的重点是，给定一个时间 x，判断「是否能把所有的衣服全部弄干」。当时间为 x 时，所有衣服能够自然蒸发 a⋅x 的湿度，于是：

• 如果 w[i]≤a⋅x：让它自然蒸发；

• 如果 w[i]>a⋅x：需要用烘干机烘干。

对于需要烘干的衣服，其剩余湿度为 t=w[i]−a⋅x，烘干次数为 t / b +(t % b == 0 ? 0 : 1) 。（向上取整）。

我们可以遍历所有的衣服，计算烘干机的「使用次数」：

• 如果烘干机使用次数「大于」给定的时间 x，说明不能全部弄干；

• 如果烘干机使用次数「小于等于」给定的时间 x，说明能全部弄干。

通过二分查找，我们可以找到最小的 ret，使得所有衣服都能在 ret 时间内被弄干。

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=5e5+10; LL n,a,b; LL w[N]; bool check(LL x) { int cnt=0; for(int i=1;i<=n;i++) { if(w[i]<=x*a) { continue; } else { int t=w[i]-x*a; cnt+=t/b+(t%b==0?0:1); } } return cnt<=x;//正常情况下cnt是小于x次的 } int main() { cin>>n>>a>>b; for(int i=1;i<=n;i++) { cin>>w[i]; } LL left=1,right=5e5;//注意这里是时间的取值范围 while(left<right) { LL mid=left+(right-left)/2; if(check(mid)==false)//说明时间太短了，才会导致烘干机使用次数变多 { left=mid+1; } else { right=mid; } } cout<<left<<endl; }

• 注意我们本质是寻找符合条件的x，而由于当 x≥ret 时，我们「能弄干」所有衣服，我们只看x的情况，我们就知道是寻找区间左端点
• 当满足 check(mid)==false时，也就是对应我们上面说的当 x<ret 时，我们「不能弄干」所有衣服，也就是说现在x < ret，我们需要增大x，但是我们是寻找区间左端点，所以此时就是left=mid+1

题目五——P3853 [TJOI2007] 路标设置 - 洛谷

根据题意，我们可以发现以下性质：

• 空旷指数是 x ，最多可增设的路标数量为K。

• 当 x 在「增大」的时候，最多能增设的路标在「减少」。

• 当 x 在「减小」的时候，最多能增设的路标在「增加」。

在整个「解空间」里面，设最小空旷指数是 ret。于是有：

• 当 x≥ret 时，最多能增设的路标<=K。

• 当 x<ret 时，最多能增设的路标>K。

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

这不就是找区间左端点吗？

那接下来的问题就是，给定一个空旷指数x，我们怎么计算出此时的最多能增设的路标呢？

d=a[i]−a[i−1]，需要的路标数量是d/x.

如果 d 能被 x 整除，即 d%x==0，此时d/x=1，会重复计数，我们需要将这个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，但是我们是寻找区间左端点，所以此时就是right=mid

题目六——P1182 数列分段 Section II - 洛谷

根据题意，我们可以发现以下性质：

• 当分的段数越多的时候，最⼤的和越⼩；

• 当分的段数越少的时候，最⼤的和越⼤。

而在本题中，我们知道的是分的段数M;

我们就得使用不断修改每段和的最大值来逼近这个段数M。

在整个「解空间」里面，设每段和的最大值是 x，而当分M段时每段和的最大值=ret。于是有：

• 当每段和的最大值x≥ret 时，分的段数的最小值<=M。

• 当每段和的最大值x<ret 时，分的段数的最小值>M。

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

注意我们找的是每段和的最大值，所以本质就是寻找区间左端点

那么问题变成了，当我给你一个每段最大和，我怎么计算出当前最少能分几段数呢？

很简单。

• 从前往后累加，只要和⼩于x，就⼀直加；
• 直到和超过x，之前的为⼀段，然后从该位置继续累加。

我们要注意这个每段和的最大值的取值范围是【单个元素里面的最大值，所有元素的和】

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; long long nums[N]; int n,m; int call(int x) { int sum=0,cnt=0; for(int i=1;i<=n;i++) { sum+=nums[i]; if(sum>x) { cnt++; sum=nums[i]; } } return cnt+1; } int main() { cin>>n>>m; long long left=0,right=0; for(int i=1;i<=n;i++) { cin>>nums[i]; left=max(left,nums[i]); right+=nums[i]; } while(left<right) { int mid=left+(right-left)/2;//注意是寻找区间左端点 if(call(mid)<=m) { right=mid; } else { left=mid+1; } } cout<<left<<endl; }

题目七——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; }