二分专题
§ 二分/折半查找
前提：数组有序
- 过程模拟：
每次都砍掉查找空间的一半 - 查找成功和查找失败：
二分的本质：删除答案不存在的区间
二分查找刷题
1.奇怪的刮刮乐
样例输入
5 5
1 3 26 7 15
15 10 3 7 2
样例输出
3 7 15
25
题目解析：将N区的数字从小到大排序，M区保持不变，遍历M区，在N区中二分查找M区的元素。注意控制输出格式，题目测试数据有点大，所以不要用cin或cout来输入输出，因为这两个的时间比printf和scanf大得多
?提交网址1?
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
//binary search
int bs(int *arr, int len, int num) {
int l = 0, r = len - 1, mid;
while (l <= r) {
mid = l + (r - l) / 2;
if (arr[mid] == num) return mid;
else if (arr[mid] > num) r = mid - 1;
else l = mid + 1;
}
return 0;
}
int m, n, x[100005], y[100005], ans[100005], cnt;
long long sum;
int main() {
freopen("input", "r", stdin);
cin >> m >> n;
for (int i = 0; i < m; i++) {
scanf("%d", &x[i]);
}
for (int i = 0; i < n; i++) {
scanf("%d", &y[i]);
}
sort(y, y + n);
for (int i = 0; i < m; i++) {
if (bs(y, n, x[i])) {
ans[cnt++] = x[i];
}
}
for (int i = 0; i < cnt; i++) {
i && printf(" ");
printf("%d", ans[i]);
sum += ans[i];
}
cout << endl << sum << endl;
return 0;
}
2.吃瓜群众
样例输入
5 3
1 3 26 7 15
26 99 3
样例输出
3
0
2
?提交网址2?
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node {
int x, id;
};
int m, n, y;
node wm[100005];
int bs(node *arr, int len, int num) {
int l = 0, r = len - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid].x == num) return mid;
else if (arr[mid].x > num) r = mid - 1;
else l = mid + 1;
}
return -1;
}
bool cmp(const node &a, const node &b) {
return a.x < b.x;
}
int main() {
//freopen("input", "r", stdin);
cin >> m >> n;
for (int i = 0; i < m; i++) {
scanf("%d", &wm[i].x);
wm[i].id = i + 1;
}
sort(wm, wm + m, cmp);
for (int i = 0; i < n; i++) {
scanf("%d", &y);
//也可以优化代码直接输出bs的返回值，从而不用判断
int t = bs(wm, m, y);
if (t == -1) printf("0\n");
else printf("%d\n", wm[t].id);
}
return 0;
}
3.吃瓜群众升级版
样例输入
5 5
1 3 26 7 15
27 10 3 4 2
样例输出
0
5
2
4
2
?提交网址3?
- 样例解释
二分查找的2种特殊情况
可以总结出这种找第一个1的特殊二分查找的套路：
while (L != R) //while (L < R);
{
mid = (L + R) / 2;
L = mid + 1;
//mid指向的有可能是1，因此mid所在的区间不能删掉
R = mid;
}
那么同理，也肯定有前面一堆1后面一堆0的找最后一个1的情况，就是上面的情况反过来
while (L != R) //while (L < R);
{
mid = (L + R + 1) / 2;
//如果分子没加1，则[1,0]情况L总是指向1，没动，陷入了一种死循环
L = mid;
//mid指向的有可能是1，因此mid所在的区间不能删掉
R = mid - 1;
}
那么上面的题目很容易就写出来了
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct node {
int ind, num;
};
node wm[100005];
int m, n;
bool cmp(const node &a, const node &b) {
return a.num < b.num;
}
int main() {
//freopen("input", "r", stdin);
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i++) {
scanf("%d", &wm[i].num);
wm[i].ind = i;
}
//虚拟瓜堆
wm[0].ind = 0;
wm[0].num = 2000000000;
sort(wm, wm + m + 1, cmp);
for (int i = 0; i < n; i++) {
int t, l = 0, r = m;
scanf("%d", &t);
while (l != r) {
int mid = (l + r) / 2;
if (wm[mid].num >= t) {
r = mid;//mid指向了1，调r
} else {
l = mid + 1;//mid指向了0，调l
}
}
printf("%d\n", wm[l].ind);
}
return 0;
}
§ 二分答案
通过下面的例题可以发现，没有给定的有序数组可以进行二分查找，因此mid所指向的是一个临时的答案，这个答案通过满足题目要求的函数算出来
刷题
4.原木切割
样例输入
3 8
6
15
22
样例输出
5
?提交网址4?
罗列出下标与答案的对应关系，由题意编写一个从下标映射到答案的函数
再分析这种是什么特殊的二分查找：找的是最后一个1（虽然题目要求的是整数，但这里用小数分析在哪边的区间答案是一样的）
确定下标的上下限：这里最小肯定为1，最大就看输入的数据的下标最大值
#include <iostream>
#include <cstdio>
using namespace std;
//堆(全局)区定义的数据都是“干净的”，初始值为0
int n, m, num[100005], mmax;
//func函数就像是一个数组一样，给定下标返回对应的值
int func(int x) {
int t = 0;
for (int i = 0; i < n; i++) {
t += num[i] / x;
}
return t;
}
int bs() {
int l = 1, r = mmax;//确定区间
while (l != r) {
int mid = (l + r + 1) / 2;
int s = func(mid);
if (s >= m) {
l = mid;
} else {
r = mid - 1;
}
}
return r;//随便返回左指针或右指针
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> num[i];
mmax = max(mmax, num[i]);
}
cout << bs() << endl;
return 0;
}
5.暴躁的程序猿
样例输入
5 3
1
2
8
4
9
样例输出
3
?提交网址5?
- 样例分析
找到下标和答案的关系：
下标——最近的两个人的距离
答案——被安排的人数
最小距离为1时5个位置都能被安排
最小距离为2时，1安排，2不能，若安排到了2则最小距离变成了1，因此这样只能安排1、4、8这3个位置
问题变成了找出最后一个1
≥m时左区间，<m时右区间
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, num[100005];
//用函数替代能安排人数的数组，如果想预处理"数组"也行
int func(int x) {
//cnt:在最小距离为x时，被安排的人数
//last:上一个人被安排的人数
int cnt = 1, last = num[0];
for (int i = 1; i < n; i++) {
if (num[i] - last >= x) {
cnt++;
last = num[i];
}
}
return cnt >= m;
}
int bs() {
int l = 1, r = num[n - 1] - num[0];
while (l != r) {
int mid = (r + l + 1) / 2;
if (func(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> num[i];
}
sort(num, num + n);
cout << bs() << endl;
return 0;
}
6.切绳子(小数二分)
套路变了：
while (r - l >= 0.001) {//舍掉两位小数的精度,至少小数点后面有2个0
mid = (l + r) / 2;
//mid = l + (r - l) / 2; //怕直接加超出了范围
l = mid;
r = mid;
}
样例输入
4 11
8.02
7.43
4.57
5.39
样例输出
2.00
?393提交地址?
- 分析
| 长度 | 8.02 | 7.43 | 4.57 | 5.39 |
|---|---|---|---|---|
| 切2.00得到的数目 | 4 | 3 | 2 | 2 |
一共能切到4+3+2+2=11
从2.00左右开始展开
| 切得的绳子长度 | 1.99 | 2.00 | 2.01 |
|---|---|---|---|
| 总共能切得的个数 | 11 | 11 | 10 |
找最后一个1的问题
#include <iostream>
#include <cstdio>
using namespace std;
int n, k;
double num[10005], mmax;
int func(double x) {
int cnt = 0;//记录切割的段数
for (int i = 1; i <= n; i++) {
cnt += num[i] / x;
}
return cnt;
}
double bs() {
double l = 0, r = mmax;//l=0虽然不严谨，但不会出现除0的情况
while (r - l > 0.0001) { //够精度了
double mid = (l + r) / 2;
int s = func(mid);
if (s >= k) {
l = mid;
} else {
r = mid;
}
}
return l;//或r
}
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> num[i];
mmax = max(mmax, num[i]);
}
double t = bs();
printf("%.2f\n", (int)(t * 100) / 100.0);
//printf("%.2f\n", t - 0.005);
return 0;
}
最后小数(如2.0056)的两种处理方式：
- 2.0056-0.005再四舍五入
- 2.0056×100转int类型再除100
7.伐木
题目ID:82
样例输入
4 9
20 17 15 10
样例输出
14
- 分析
设定高度20、17、15、10
| 高度 | 10 | 12 | 13 | 14 | 15 | 16 | 17 | 18 |
|---|---|---|---|---|---|---|---|---|
| 切割长 | 22 | 16 | 12 | 10 | 7 | 5 | 3 | 2 |
9在对应的高度在14和15之间，输出的答案往左走才找到了真正的1
因此问题是前面一堆1后面一堆0的问题
- 确定上下界：0 木头的最高长度
- mid→临时答案→高度
- 111100000
#include <iostream>
#include <cstdio>
using namespace std;
int n, m;
long long num[1000005], maxn;
//当锯的高度设定为x时切割下来的总长度
long long func(int x) {
long long ans = 0;
for (int i = 0; i < n; i++) {
if (num[i] > x)
ans += num[i] - x;
}
return ans;
}
int bs() {
int l = 0, r = maxn;
while (l != r) {
int mid = (l + r + 1) / 2;
long long s = func(mid);
if (s >= m) l = mid;
else r = mid - 1;
}
return l;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
scanf("%d", &num[i]);
maxn = max(maxn, num[i]);
}
cout << bs() << endl;
return 0;
}
8.数列分段
题目ID:391
样例输入
5 3
4
2
4
5
1
样例输出
6
列表分析：
| 最大和 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|
| 分段数 | 5 | 3 | 3 | 3 | 3 | 2 | 2 |
满足单调性
- 上限下限：
max{num[i]}，所有数字的累加 - mid临时答案→最大和
- 特殊情况找第一个1
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, num[100005], minn = 100000000;
long long maxn;
//过脑子：所有涉及到累加的才应该改成 long long 类型
int func(long long x) {
long long now = 0;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (now + num[i] > x) {
// 超过x，则记录一段，并且从当前值重新开始加
cnt++;
now = num[i];
} else if (now + num[i] == x) {
//正正好好等于x，则从下一个数字开始
cnt++;
now = 0;
} else {
now += num[i];
}
}
if (now != 0) cnt++; //手动处理一下可能留下的最后一段的值
return cnt;
}
long long bs() {
long long l = minn, r = maxn;
while (l != r) {
long long mid = (l + r) / 2;
int s = func(mid);
if (s <= m) r = mid;
else l = mid + 1;
}
return l;
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
scanf("%lld", &num[i]);
maxn += num[i];
minn = min(minn, num[i]);
}
cout << bs() << endl;
return 0;
}
9.跳石头
题目ID:394
样例输入
25 5 2
2
11
14
17
21
样例输出
4
| 最短距离 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 最少移走石头数量 | 0 | 0 | 1 | 2 | 3 | 3 | 4 |
#include <iostream>
#include <cstdio>
using namespace std;
int maxn, n, m, num[50005];
int func(int x) {
int cnt = 0, last = 0;
for (int i = 1; i <= n + 1; i++) {
if (num[i] - last >= x) {
last = num[i];
}
else {
cnt++;
}
}
return cnt;
}
int bs() {
int l = 1, r = maxn;
while (l != r) {
int mid = (l + r + 1) / 2;
int s = func(mid);
if (s <= m) l = mid;
else r = mid - 1;
}
return l;
}
int main() {
cin >> maxn >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%d", &num[i]);
}
num[n + 1] = maxn;
cout << bs() << endl;
return 0;
}
专题小结
二分答案的本质就是二分查找的特殊情况，一般出现“最大的最小”“最小的最大”等字眼的题目肯定就是二分答案的题目，煮了很多栗子能找到做题分析的套路：答案作为下标，下标对应的函数值写成一个函数
更多练习：392丢瓶盖、395复制书稿