二分

学习
字数统计: 2.7k   |   阅读时长≈ 13 分钟

二分答案

0. 概述

  • 将答案区间进行二分搜索， 每次取区间中间值出来用于尝试是否满足题目性质，不断缩小调整区间，直到确定最终答案为止
  • 有单调性的题目一定可以二分，但是用二分做的题目不一定拥有单调性。
  • 注意：二分一定是有解的，不可能无解，无解永远是题目的无解而不是二分的无解。

1. 解二分题步骤

  • 题目出现求最值，首先想到二分/贪心/动态规划等算法
  • 题目具有单调性，则可以考虑用二分求解
  • 若求满足某个性质的数第一次出现，或求最小值 → 答案在左边 → 满足性质时压缩右边界 → 二分出来的答案一定在 $l$ 上
1
2
3
4
5
6
7
8
// 答案在左边
while(l<=r) {
    int mid=l+r>>1;
    // 压缩右边界
    if(check(mid)) r=mid-1;
    else l=mid+1;
}
cout<<l<<endl; // 答案在左边界上
  • 若求满足某个性质的数最后一次出现，或求最大值 → 答案在右边 → 满足性质时压缩左边界 → 二分出来的答案一定在 $r$ 上
1
2
3
4
5
6
7
8
// 答案在右边
while(l<=r) {
    int mid=l+r>>1;
    // 压缩左边界
    if(check(mid)) l=mid+1;
    else r=mid-1;
}
cout<<r<<endl; // 答案在右边界上

2. 整数二分

2.1. 洛谷 P2440.木材加工

题目链接：P2440 木材加工 - 洛谷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e5+5;
int n,k; // 原木/要的根数
int a[N]; // 每根木头的长度

bool check(int x) {
	int cnt=0;
	// 如果切出来的数量满足k根说明切够了
	for(int i=1;i<=n;i++) {
		cnt+=a[i]/x;
		if(cnt>=k) return true;
	}
	return false;
}

int main() {
	cin>>n>>k;
	int mmax;
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);
		mmax=max(mmax,a[i]); // 找最大木头数,作为r的初值
	}
	int l=1; // 此时切出来最多,每根都能切成a[i]份
	int r=mmax; // 此时切出来最少,只能切一根
	// 找最大值,答案在右边,压缩左边界,答案在r上
	while(l<=r) {
		int mid=l+r>>1;
		if(check(mid)) {
			l=mid+1;
		} else {
			r=mid-1;
		}
	}
	cout<<r<<endl; // 答案一定在r上且r一定比l小1
	return 0;
}

2.2. 洛谷 P1873.EKO/砍树

题目链接：P1873 EKO / 砍树 - 洛谷 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e6+5;
int n,m; // n:树的数量,m:所需总长度
int a[N]; // 存储每棵树的高度

bool check(int x) {
	ll cnt=0; // 切出来的长度爆int,题目也说超过M
	for(int i=1;i<=n;i++) {
		if(a[i]-x>0)
			cnt+=a[i]-x;
	}
	if(cnt>=m) return true;
	return false;
}

int main() {
	cin>>n>>m;
	int mmax; // 存储最大高度作为r的初始值
	for(int i=1;i<=n;i++) {
		scanf("%d",&a[i]);	
		mmax=max(mmax,a[i]);
	}
	int l=1; // 此时每棵树能切出来的长度都是a[i],切得最多
	int r=mmax; // 此时每棵树能切出来的高度都是0,切得最少
	// l能取0吗?如果停在l=0,那么r一定等于-1,此时有问题
	// 找锯片的最大高度,压缩左边界,答案在r上
	while(l<=r) {
		int mid=l+r>>1;
		if(check(mid)) l=mid+1;
		else r=mid-1;
	}
	cout<<r<<endl;
	return 0;
}

2.3. 洛谷 P1678.烦恼的高考志愿

题目链接：P1678 烦恼的高考志愿 - 洛谷 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 开ll不然过不了

const ll N=1e5+5;
ll n,m;
ll a[N]; // 存储学校的分数线
ll b[N]; // 存储每个同学的估分

int main() {
	cin>>n>>m;
	// n个学校,m个同学
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&a[i]);	
	}
	for(ll i=1;i<=m;i++) {
		scanf("%lld",&b[i]);
	}
	sort(a+1,a+1+n);
	ll cnt=0;
	// 遍历所有同学
	for(ll i=1;i<=m;i++) {
		// 卫语言风格
		// 比最小值还小,跳过
		if(b[i]<=a[1]) {
			cnt+=abs(b[i]-a[1]);
			continue;
		}
		else if(b[i]>=a[n]) {
			cnt+=abs(b[i]-a[n]);
			continue;
		}
		ll l=1,r=n; // 边界是[1,n]
		while(l<=r) {
			ll mid=l+r>>1;
			// 注意找第一个是答案在左边的问题,所以要压缩右边界
			// 找第一个大于等于b[i]的第一个学校的分数线,答案在左边,即a[l]
			// 那么最后一个小于b[i]的元素的下标就应该是a[l-1]
			if(a[mid]>=b[i])
				r=mid-1;
			else
				l=mid+1;
		}
		// 取二者之中的最小值
		cnt+=min(abs(a[l]-b[i]),abs(a[l-1]-b[i]));
	}
	cout<<cnt;
	return 0;
}

2.4. 蓝桥杯 23省b 冶炼金属

题目链接：P9240 [蓝桥杯 2023 省 B] 冶炼金属 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e4+5;
int n;
int a[N]; // 存储每次投入的金属数量
int b[N]; // 存储每次冶炼出的特殊金属数量

bool check_1(int mid) {
	for(int i=1;i<=n;i++) {
		if(a[i]/mid>b[i])	
			return false;
	}
	return true;
}

bool check_2(int mid) {
	for(int i=1;i<=n;i++) {
		if(a[i]/mid<b[i])
			return false;
	}
	return true;
}

int main() {
	cin>>n;
	int mmax=INT_MIN;
	for(int i=1;i<=n;i++) {
		scanf("%d%d",&a[i],&b[i]);	
		mmax=max(mmax,a[i]); // 最大的普通金属数量
	}
//	cout<<"最大值是"<<mmax<<endl;
	int l=1; // 转换率最小为1,有多少转换多少
	int r=mmax; // 最小只能转换出一个
	// 找最小值,压缩右边界,答案在l上
	while(l<=r) {
		int mid=(ll)l+r>>1;
		if(check_1(mid)) {
			r=mid-1;
		} else {
			l=mid+1;
		}
	}
	cout<<l<<' ';
	l=1,r=mmax;
	// 找最大值,压缩左边界,答案在r上
	while(l<=r) {
		int mid=(ll)l+r>>1;
		if(check_2(mid)) {
			l=mid+1;
		} else {
			r=mid-1;
		}
	}
	cout<<r<<endl;
	return 0;
}

3. 浮点二分

3.1. AcWing 790. 数的三次方根

题目链接：790. 数的三次方根 - AcWing题库

  • 对于开二次方根，因为开出来一定是正数，所以可以设置$l=0$，$r=x$，但是三次方根可能有负数，不能单纯的取 $l=-x$，$r=x$，这样的话输入的$x$是正数，范围是$[-x,x]$，输入的数是负数，范围是$[x,-x]$就会出大问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int main() {
	double x;
	cin>>x;
	// 因为是开三次方根,所以要考虑负数的情况
    // 注意
	double l=-100000,r=100000;
	// 保留6位小数就1e-8(基于经验),同理保留4位就1e-6
	while(r-l>1e-8) {
		double mid=(l+r)/2;
		if(mid*mid*mid>=x)
			r=mid;
		else
			l=mid;
	}
	cout<<setprecision(6)<<fixed<<l<<endl;
	return 0;
}

4. 加深理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair<int,int> PII;

// 解题思路: 

const int N=1e5+5;
int a[]={0,1,2,4,3,7,6,3,4,8,9};


int main() {
	sort(a+1,a+10);
	// 下标
	for(int i=1;i<=10;i++) {
		if(i==1) cout<<"下标:";
		cout<<i<<' ';
	}
	cout<<endl;
	for(int i=1;i<=10;i++) {
		if(i==1) cout<<"数值:";
		cout<<a[i]<<' ';
	}
	
	int l=1,r=10; // 下标边界
	cout<<endl;
	// 1)找第一个大于等于3的元素的下标,看是3还是4呢?
	while(l<=r) {
		int mid=l+r>>1;
		if(a[mid]>=3) r=mid-1;
		else l=mid+1;
	}
	cout<<"1)找第一个大于等于3的元素的下标:>"<<endl;
	cout<<l<<' '<<r<<" 答案是:"<<a[l]<<endl;
	// 找最小值,答案是l,r一定是l-1
	// 2)找第一个大于3的元素的下标,是5吧而不是6吧
	l=1,r=10;
	while(l<=r) {
		int mid=l+r>>1;
		if(a[mid]>3) r=mid-1;
		else l=mid+1;
	}
	cout<<"2)找第一个大于3的元素的下标:>"<<endl;
	cout<<l<<' '<<r<<" 答案是:"<<a[l]<<endl;
	// 3)找第一个大于等于2且小于等于4的元素的下标,是5而不是4吧
	l=1,r=10;
	while(l<=r) {
		int mid=l+r>>1;
		if(2<=a[mid] && a[mid]<=4) r=mid-1;
		else l=mid+1;
	}
	cout<<"3)找第一个大于等于2且小于等于4的元素的下标:>"<<endl;
	cout<<l<<' '<<r<<" 答案是:"<<a[l]<<endl;
	// 4)找最后一个小于等于4的元素
	// 压缩l,答案一定在r上,此时l必为r+1
	l=1,r=10;
	while(l<=r) {
		int mid=l+r>>1;
		if(a[mid]<=4) l=mid+1;
		else r=mid-1;
	}
	cout<<"4)找最后一个小于等于4的元素的下标:>"<<endl;
	cout<<l<<' '<<r<<" 答案是:"<<a[r]<<endl;
	// 5)找最后一个小于6的元素,下标为7,答案在r
	l=1,r=10;
	while(l<=r) {
		int mid=l+r>>1;
		if(a[mid]<7) l=mid+1;
		else r=mid-1;
	}
	cout<<"5)找最后一个小于6的元素的下标:>"<<endl;
	cout<<l<<' '<<r<<" 答案是:"<<a[r]<<endl;
	// 6)找最后一个大于2且小于等于8的元素,值是8
	l=1,r=10;
	while(l<=r) {
		int mid=l+r>>1;
		if(a[mid]>2 && a[mid]<=8) l=mid+1;
		else r=mid-1;
	}
	cout<<"6)找最后一个大于2且小于等于8的元素的下标:>"<<endl;
	cout<<l<<' '<<r<<" 答案是:"<<a[r]<<endl;
	return 0;
}
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2015-2024 John Doe
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信