当前位置：首页 > news >正文

【算法】二分

news 来源：原创 2025/6/7 18:24:44

二分

1.二分查找
- 1.在排序数组中查找元素的第一个和最后一个位置
- 2.牛可乐和魔法封印
- 3.A-B 数对
- 4.烦恼的高考志愿
2.二分答案
- 1.木材加工
- 2.砍树
- 3.跳石头

1.二分查找

当我们的解具有二段性（根据最终答案所在的位置判断是否具有二段性）时，就可以使用二分算法找出答案：

根据待查找区间的中点位置，分析答案会出现在哪一侧。
接下来舍弃一半的待查找区间，转而在有答案的区间内继续使用二分算法查找结果。

在这里插入图片描述

1.在排序数组中查找元素的第一个和最后一个位置

在排序数组中查找元素的第一个和最后一个位置

在这里插入图片描述

解法：二分

class Solution 
{
public:vector<int> searchRange(vector<int>& nums, int target) {int n = nums.size();//处理边界情况if(n == 0) return {-1, -1};//1.求起始位置int left = 0, right = n - 1;while(left < right){int mid = (right + left) / 2;if(nums[mid] >= target) right = mid;else left = mid + 1;}//left和right所指的位置可能不是最终结果if(nums[left] != target) return {-1, -1};int begin = left; //记录起始位置//2.求终止位置left = 0, right = n - 1;while(left < right){int mid = (left + right + 1) / 2;if(nums[mid] <= target) left = mid;else right = mid - 1;}int end = right; //记录终止位置return {begin, end};}
};

2.牛可乐和魔法封印

牛可乐和魔法封印

在这里插入图片描述

解法：二分

二分查找算法模版题，直接上手模版即可。但是需要注意，有可能并没有这个区间，需要在二分结束之后判断一下。

#include<iostream>
using namespace std;const int N = 1e5 + 10;int n;
int a[N];int BinarySearch(int x, int y)
{int left = 1, right = n;//查找大于等于x所在的位置while(left < right){int mid = (left + right) / 2;if(a[mid] >= x) right = mid;else left = mid + 1;}if(a[left] < x) return 0;int begin = left;//查找小于等于y所在的位置left = 1, right = n;while(left < right){int mid = (left + right + 1) / 2;if(a[mid] <= y) left = mid;else right = mid - 1;}if(a[left] > y) return 0;int end = right;return end - begin + 1;
}int main()
{cin >> n;for(int i = 1; i <= n; i++) cin >> a[i];int q; cin >> q;while(q--){int x, y; cin >> x >> y;cout << BinarySearch(x, y) << endl;}return 0;
}

3.A-B 数对

P1102 A-B 数对

在这里插入图片描述

解法：排序 + 二分

由于顺序不影响最终结果，所以可以先把整个数组排序。由 A - B = C 得：B = A - C，由于 C 是已知的数，我们可以从前往后枚举所有的 A，然后去前面找有多少个符合要求的 B，正好可以用二分快速查找出区间的长度。

#include<iostream>
#include<algorithm>
using namespace std;typedef long long LL;const int N = 2e5 + 10;LL n, C;
LL a[N];int BinarySearch(int target)
{//查找target左端点int left = 1, right = n;while(left < right){int mid = (left + right) / 2;if(a[mid] >= target) right = mid;else left = mid + 1;}if(a[left] != target) return 0;  //找不到返回0int begin = left;//查找target右端点left = 0, right = n;while(left < right){int mid = (left + right + 1) / 2;if(a[mid] <= target) left = mid;else right = mid - 1;}int end = right;return end - begin + 1;
}int main()
{cin >> n >> C;for(int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);//枚举所有的ALL ret = 0;for(int i = 1; i <= n; i++) {LL B = a[i] - C;ret += BinarySearch(B);}cout << ret;return 0;
}

【STL的使用】

lower_bound：传入要查询区间的左右迭代器（注意是左闭右开的区间，如果是数组就是左右指针）以及要查询的值 k，然后返回该数组中 ≥ k 的第一个位置。
upper_bound：传入要查询区间的左右迭代器（注意是左闭右开的区间，如果是数组就是左右指针）以及要查询的值 k，然后返回该数组中 > k 的第一个位置。

比如：a = [10, 20, 20, 20, 30, 40] ，设下标从 1 开始计数，在整个数组中查询 20：

lower_bound(a + 1, a + 1 + 6, 20) ，返回 a + 2 位置的指针。
upper_bound(a + 1, a + 1 + 6, 20) ，返回 a + 5 位置的指针。
然后两个指针相减，就是包含 20 这个数区间的长度。

在这里插入图片描述
【注意】：STL用起来很爽，但是 STL 的使用范围很「局限」，查询「有序序列」的时候才有用，数组无序的时候就无法使用。但是二分模板也能在「数组无序」的时候使用，只要有「二段性」即可。

#include<iostream>
#include<algorithm>
using namespace std;typedef long long LL;const int N = 2e5 + 10;LL n, C;
LL a[N];int main()
{cin >> n >> C;for(int i = 1; i <= n; i++) cin >> a[i];sort(a + 1, a + 1 + n);//枚举所有的ALL ret = 0;for(int i = 1; i <= n; i++) {LL B = a[i] - C;ret += upper_bound(a + 1, a + 1 + n, B) - lower_bound(a + 1, a + 1 + n, B);}cout << ret;return 0;
}

4.烦恼的高考志愿

P1678 烦恼的高考志愿

在这里插入图片描述

解法：排序 + 二分

先把学校的录取分数「排序」，然后针对每一个学生的成绩 b，在「录取分数」中二分出 ≥ b 的「第一个」位置 pos，那么差值最小的结果要么在 pos 位置，要么在 pos - 1 位置。取 abs(a[pos] − b) 与abs(a[pos − 1] − b) 两者的「最小值」即可。

细节问题：

如果所有元素都大于 b 的时候，pos − 1 会在 0 下标的位置，有可能结果出错。
如果所有元素都小于 b 的时候，pos 会在 n 的位置，此时结果倒不会出错，但是我们要想到这个细节问题，这道题不出错不代表下一道题不出错。

加上两个左右护法，结果就不会出错了。

#include<iostream>
#include<algorithm>
using namespace std;typedef long long LL;const int N = 1e5 + 10;int m, n;
LL a[N];//查找大于等于b的最小值，返回该值所在数组的下标
int find(int b)
{int left = 1, right = m;while(left < right){int mid = (left + right) / 2;if(a[mid] >= b) right = mid;else left = mid + 1;}return left;
}int main()
{cin >> m >> n;for(int i = 1; i <= m; i++) cin >> a[i];sort(a + 1, a + 1 + m);//加上左护法a[0] = -1e7 - 10;LL ret = 0;while(n--){LL b; cin >> b;int pos = find(b);ret += min(abs(a[pos] - b), abs(a[pos - 1] - b));}cout << ret << endl;return 0;
}

2.二分答案

准确来说，应该叫做「二分答案 + 判断」。

二分答案可以处理大部分「最大值最小」以及「最小值最大」的问题。如果「解空间」在从小到大的「变化」过程中，「判断」答案的结果出现「二段性」，此时我们就可以「二分」这个「解空间」，通过「判断」，找出最优解。
刚接触的时候，可能觉得这个「算法原理」很抽象。没关系，3 道题的练习过后，你会发现这个「二分答案」的原理其实很容易理解，重点是如何去「判断」答案的可行性。

1.木材加工

P2440 木材加工

在这里插入图片描述

解法：二分

学习「二分答案」这个算法，基本上都会把这道比较简单的题当成例题。
设要切成的长度为 x，能切成的段数为 c 。根据题意，我们可以发现如下性质：

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

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

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

在解空间中，根据 ret 的位置，可以将解集分成两部分，具有「二段性」，那么我们就可以「二分答
案」。当我们每次二分一个切成的长度 x 的时候，如何算出能切的段数 c ？很简单，遍历整个数组，针对每一根木头，能切成的段数就是 a[i] / x。

#include<iostream>
using namespace std;typedef long long LL;const int N = 1e5 + 10;LL n, k;
LL a[N];//计算当切割长度为 x 的时候，最多能切出来多少段
LL calc(LL x)
{LL cnt = 0;for(int i = 1; i <= n; i++){cnt += a[i] / x;}return cnt;
}int main()
{cin >> n >> k;for(int i = 1; i <= n; i++) cin >> a[i];LL left = 0, right = 1e8;while(left < right){LL mid = (left + right + 1) / 2;if(calc(mid) >= k) left = mid;else right = mid - 1;}cout << left << endl;return 0;
}

2.砍树

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 int 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 = 1, right = 4e5;while(left < right){LL mid = (left + right + 1) / 2;if(calc(mid) >= m) left = mid;else right = mid - 1;}cout << left << endl;return 0;
}

3.跳石头

P2678 [NOIP2015 提高组] 跳石头

在这里插入图片描述

解法：二分

设每次跳的最短距离是 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; ){int j = i + 1;while(j <= n && a[j] - a[i] < x) j++;ret += j - i - 1;i = j;}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;
}

二分

1.二分查找

1.在排序数组中查找元素的第一个和最后一个位置

2.牛可乐和魔法封印

3.A-B 数对

4.烦恼的高考志愿

2.二分答案

1.木材加工

2.砍树

3.跳石头

相关文章：