整数二分

单调递增找x或x后继

1
2
3
4
5
6
7
8
9
int bin_search(int *a, int n, intx){
    int left = 0, right = n;
    while(l < r){
        int mid = (l + r) >> 1;
        if(a[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l;
}

单调递增找x或x前驱

1
2
3
4
5
6
7
8
9
int bin_search(int *a, int n, intx){
    int left = 0, right = n;
    while(l < r){
        int mid = (l + r) >> 1;
        if(a[mid] <= x) l = mid;
        else r = mid - 1;
    }
    return l;
}

不建议用 (l + r) / 2 因为”/“不是真正意义上的向下取证 而是 向0取整 当l+r是正数时是向下取整，当l+r是负数时，时向上取整 故推荐用右移的方式

x >> n x右移n 即二进制下所有数向右移动n位 在十进制下就是
$$
x/2^n
$$
左移则反之

例题：

P1824 [USACO05FEB] 进击的奶牛 Aggressive Cows G

题目描述

农夫约翰建造了一座有 $n$ 间牛舍的小屋，牛舍排在一条直线上，第 $i$ 间牛舍在 $x_i$ 的位置，但是约翰的 $m$ 头牛对小屋很不满意，因此经常互相攻击。约翰为了防止牛之间互相伤害，因此决定把每头牛都放在离其它牛尽可能远的牛舍。也就是要最大化最近的两头牛之间的距离。

牛们并不喜欢这种布局，而且几头牛放在一个隔间里，它们就要发生争斗。为了不让牛互相伤害。约翰决定自己给牛分配隔间，使任意两头牛之间的最小距离尽可能的大，那么，这个最大的最小距离是多少呢？

输入格式

第一行用空格分隔的两个整数 $n$ 和 $m$；

下面 $n$ 行为 $n$ 个用空格隔开的整数，表示位置 $x_i$。

输出格式

一行一个整数，表示最大的最小距离值。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
5 3
1
2
8
4
9

输出 #1

1
3

说明/提示

【样例解析】把牛放在 $1$，$4$，$8$ 这三个位置，距离是 $3$。容易证明最小距离已经最大。

【数据范围】对于 $100%$ 的数据，$2 \le n \le 10^5$，$0 \le x_i \le 10^9$，$2 \le m \le n$。不保证 $x$ 数组单调递增。

解答

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
#include<bits/stdc++.h>
using namespace std;

int n, m;
int x[100005];

bool check(int d){
	int cnt = 1;
	int last_pos = x[1];
	for(int i = 2; i <= n; i++){
		if(x[i] - last_pos >= d){
			last_pos = x[i];
			cnt++;
		}
	}
	return cnt >= m;
}


int main(){
	
	scanf("%d %d",&n, &m);
	for(int i = 1; i <= n; i++){
		scanf("%d",&x[i]);
	}
	
	sort(x+1,x+n+1);
	
	int l = 1, r = x[n] - x[1] + 1;
	int ans;
	while(l < r){
		int mid = (l + r) >> 1;
		if(check(mid)){
			ans = mid;
			l = mid + 1;
		}else{
			r = mid;
		}
	}
	
	cout << ans;
	return 0;
}

注意 需要让L,R的范围囊括所有可能 一般让R取最大值+1 以防漏掉有边界

实数二分

P1577 切绳子

题目描述

有 $N$ 条绳子，它们的长度分别为 $L_i$。如果从它们中切割出 $K$ 条长度相同的绳子，这 $K$ 条绳子每条最长能有多长？答案保留到小数点后 $2$ 位(直接舍掉 $2$ 位后的小数)。

输入格式

第一行两个整数 $N$ 和 $K$，接下来 $N$ 行，描述了每条绳子的长度 $L_i$ 。

输出格式

切割后每条绳子的最大长度。答案与标准答案误差不超过 $0.01$ 或者相对误差不超过 $1%$ 即可通过。

输入输出样例 #1

输入 #1

1
2
3
4
5
4 11
8.02
7.43
4.57
5.39

输出 #1

1
2.00

说明/提示

对于 $100%$ 的数据 $0<L_i\leq 100000.00,0<n\leq 10000,0<k\leq 10000$

解答

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
#include<bits/stdc++.h>
using namespace std;

int n, k;
double ll[10005];

bool check(double mid){
	int cnt = 0;
	for(int i = 1; i <= n; i++){
		cnt += (int)(ll[i] / mid);
	}
	return cnt >= k;
}

int main(){
	double maxx = -1;
	scanf("%d %d",&n,&k);
	for(int i = 1; i <= n; i++){
		scanf("%lf",&ll[i]); 
		if(ll[i] > maxx) maxx = ll[i];
	}
	double l = 0, r = maxx;
	while((r - l) > 1e-3){
		double mid = l + (r - l) / 2;
		if(check(mid))l = mid;
		else r = mid;
	}
	
	printf("%.2f",l);
	return 0;
}

while的循环条件是精度