YuriCode
0%

二分答案法

发表于 更新于 分类于
本文字数： 2.5k 阅读时长 ≈ 2 分钟

二分答案法

1、估计最终答案可能范围是什么
2、分析问题的答案和给定条件的单调性，大部分的时候只需要用到自然智慧
3、建立一个f函数，当答案固定的情况下，判断给定的条件是否达标
4、在最终答案可能的范围内不断二分搜索，每次用f函数判断，直到二分结束，找到最合适的答案

经典题目

进击的奶牛

https://www.luogu.com.cn/problem/P1824

分析过程
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
//隔间位置 1 2 4 8 9
//最小可能距离l = 1
//最大可能距离r = 9 - 1 = 8
//l...mid...r
//将mid = (1 + 8) / 2 = 4作为最小距离

//第一次二分尝试
//mid = 4

//第一头牛放在隔间1
//第二头牛放在距离隔间1至少4的下一个隔间
//2 - 1 = 1 (x)
//4 - 1 = 3 (x)
//8 - 1 = 7 (o)
//第二头牛放在隔间4
//第三头牛放在距离隔间4至少4的下一个隔间
//9 - 8 = 1 (x)
//无法放置第三头牛，尝试更小的距离
//r = mid - 1 = 3

//第二次二分尝试
//mid = (1 + 3) / 2 = 2

//第一头牛放在隔间1
//第二头牛放在距离隔间1至少3的下一个隔间
//2 - 1 = 1 (x)
//4 - 1 = 3 (o)
//第二头牛放在隔间3
//第三头牛放在距离隔间3至少4的下一个隔间
//8 - 4 = 3 (o)
//第三头牛放在隔间4
//尝试更大距离
//l = mid + 1 = 3

//第三次二分尝试
//mid = (3 + 3) / 2 = 3
//第一头牛放在隔间1
//第二头牛放在距离隔间1至少3的下一个隔间
//2 - 1 = 1 (x)
//4 - 1 = 3 (o)
//第二头牛放在隔间3
//第三头牛放在距离隔间3至少4的下一个隔间
//8 - 4 = 3 (o)
//第三头牛放在隔间4
//尝试更大距离
//l = mid + 1 = 4

//l > r时退出循环
//ans = 3
题解
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
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int N, C;
int arr[100006];

//检查是否可按最小距离放置C头牛
bool check(int mid) {
	int count = 1;      //已放置的牛数
	int last = arr[0];  //上一头牛的位置
	for (int i = 1; i < N; i++) {
		if (arr[i] - last >= mid) {
			count++;
			last = arr[i];
			if (count == C) return 1;
		}
	} 
	return 0;   
}

//求最大最小距离
int BS(){
	int l = 1;         			  //最小可能距离
	int r = arr[N - 1] - arr[0];  //最大可能距离
	int ans = 0;
	while(l <= r) {
		int mid = (l + r) / 2;
		if (check(mid)) {
			ans = mid;
			l = mid + 1;    //尝试更大的最小距离
		} else {
			r = mid - 1;    //尝试更小的最大距离
		}
	}
	return ans;
}


int main()
{	
	cin >> N >> C;
	
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i]);
	}
	sort(arr, arr + N);
	cout << BS() << endl;

	return 0;
}

跳石头

https://www.luogu.com.cn/problem/P2678

题解
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
#include <iostream>
#include <cstdio>
using namespace std;

int L, N, M;
int arr[50005];

//检测是否可以移走所有距离小于最短跳跃距离的石头
bool check(int d) {
	int pre = 0;//上一个未移除的石头的位置
	int count = 0;
	//这里不能直接遍历整个数组，因为可能会移除终点处的石头
	for (int i = 1; i <= N; i++) {
		if (arr[i] - pre < d) {
			count++;
		} else {
			pre = arr[i];  //更新上一个未移除的石头位置
		}
	}
	if (arr[N + 1] - pre < d) count++;
	return count <= M; 
} 

//找到最大最小距离
int BS(){
	int l = 1;
	int r = L;
	int ans = 0;
	while (l <= r) {
		int mid = (l + r) / 2;
		if (check(mid)) {
			ans = mid;
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return ans;
}

int main()
{
	
	cin >> L >> N >> M;
	for (int i = 1; i <= N; i++) {
		scanf("%d", &arr[i]);
	}
	arr[0] = 0;
	arr[N + 1] = L;
	cout << BS() << endl;
	
	
	return 0;
}