day5

Uncategorized
2.4k words

day5 - 更上一层楼

二分

二分查找

二分查找

  1. 闭区间 [l, r]

注意求mid的三种解法

(1) mid = (l + r)/2

(2) mid = (l + r)>>1

(3) mid = l + (r - l)/2

思考三种写法的不同用处

  1. 左闭右开 [l, r)
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
#include <bits/stdc++.h> 
using namespace std;
int main(){
    int n,a[1000000] = {0},x,r; 
    int i,j,mid,left,right; 
    cin>>n;
    //读入数组元素
    for(i = 0;i < n;i++){ 
        cin>>a[i];
    }
    cin>>x;
    left = 0;
    right = n - 1;
    ans = -1;//假设没找到
    //当还有求解范围时
    while(left < right){
        //中间下标
        mid = (left + right) >> 1;
        if(a[mid] == x) {
            ans = mid;
            break;
        }else 
        if(x < a[mid]){
            right = mid;
        }else 
        if(x > a[mid]){ 
            left = mid + 1;
        }
    }
    //输出位置 
    cout<<(ans == -1?-1:ans+1)<<endl;
    return 0;
}

二分查找边界

有一种情况，当数据出现多个相同的数字是，二分查找应该返回哪一个位置?

例如：

n = 5

a[] = {1, 1, 1, 1, 1}

x = 1

返回 ans = 3

显然这种二分查找只会优先返回相同数字中间的位置或偏左一位，但是我们通常想要的是第一个或这是最后一个相同数字的位置

  1. 二分查找左边界

道理其实很简单：我们在找到x的时候a[mid] == x,还要向左边看，向左折半查找，等同与 if(x == a[mid]) right = mid - 1,然后和 if(x < a[mid]) right = mid - 1合并一下,就是 if(x <= a[mid]) right = mid - 1了

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
#include <bits/stdc++.h> 
using namespace std;
int a[1000000] = {0};//太大的数组要放到全局变量去
int main(){
    int n,x; 
    int i,j,mid,left,right; 
    cin>>n;
    //读入数组元素
    for(i = 0;i < n;i++){ 
        cin>>a[i];
    }
    cin>>x;
    left = 0;
    right = n - 1;
    //当还有求解范围时
    while(left <= right){
        //中间下标
        mid = (left + right) / 2;
        if(x <= a[mid]){
            right = mid - 1;
        }else 
        if(x > a[mid]){ 
            left = mid + 1;
        }
    }
    //输出位置 
    cout<<(a[left] == x?left+1:-1)<<endl;
    return 0;
}
  1. 二分查找右边界

同理可得

例题1：洛谷题号1678

烦恼的高考志愿

题目背景

计算机竞赛小组的神牛 V 神终于结束了高考，然而作为班长的他还不能闲下来，班主任老 t 给了他一个艰巨的任务：帮同学找出最合理的大学填报方案。可是 v 神太忙了，身后还有一群小姑娘等着和他约会，于是他想到了同为计算机竞赛小组的你，请你帮他完成这个艰巨的任务。

题目描述

现有 $m$ 所学校，每所学校预计分数线是 $a_i$。有 $n$ 位学生，估分分别为 $b_i$。

根据 $n$ 位学生的估分情况，分别给每位学生推荐一所学校，要求学校的预计分数线和学生的估分相差最小（可高可低，毕竟是估分嘛），这个最小值为不满意度。求所有学生不满意度和的最小值。

输入格式

第一行读入两个整数 $m,n$。$m$ 表示学校数，$n$ 表示学生数。

第二行共有 $m$ 个数，表示 $m$ 个学校的预计录取分数。第三行有 $n$ 个数，表示 $n$ 个学生的估分成绩。

输出格式

输出一行，为最小的不满度之和。

样例 #1

样例输入 #1

1
2
3
4 3
513 598 567 689
500 600 550

样例输出 #1

1
32

提示

数据范围：

对于 $30%$ 的数据，$1\leq n,m\leq1000$，估分和录取线 $\leq10000$；

对于 $100%$ 的数据，$1\leq n,m\leq100000$，估分和录取线 $\leq 1000000$ 且均为非负整数。

这题是二分查找的标准例题。

一般枚举算法的思路：两层循环，对每一位同学从头到尾搜索学校，找到分值相差最小的学校，使得总不满意度最小。时间复杂度O(n*m)

二分答案的思路:

这不是一般二分查找，不一定能找到估分和学校分数相同的情况。先将学校排序，成为单调的问题，从小到大，再单纯的二分法，分数大于mid，向右寻找，分数小于mid，向左寻找。如此最后left停在了刚好左边小，右边大的位置，也就是分数相近，比较左右不满意值，累加起来。时间复杂度O(n*logm)

关于快排：

1
sort(a+1,a+m+1);//对学校分数快速排序

这个是C++中algorithm库中的快排函数sort(),能从小到大排序。

关键代码：(选择什么样二分的形式)

1
2
3
4
5
6
7
8
9
10
int l=1,r=m;
while(l<=r){
    int mid =(r+l)/2;
        if(x<=a[mid])
            r = mid - 1;
        else
            l = mid + 1;
    }
    
sum += min(a[l]-x,x-a[l-1]);

有没有特殊情况：不用二分的(这样可以优化算法,相当于剪枝)

最后，这题有没有别的做法：比如排序？

二分答案

二分答案与二分查找类似，也就是对这有单调性的答案进行二分，用于求解满足某种条件下的最大(小)值

二分答案的常见模版:

1
2
3
4
5
6
7
8
int l=1,r=max;
while(l<=r){
    int mid = (l + r)/2;
    if(check(mid))//check函数是自己写的
        r = mid-1;
    else
        l = mid+1;
}

例题2：洛谷题号1676 1824(双倍经验)

[USACO05FEB] Aggressive cows G

题目描述

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

1
2
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$。

不保证 $a$ 数组单调递增。

做题思路：

二分答案的核心是：存在一个分界线（即答案ans），大于 ans 时没有合法答案；小于等于 ans 时，一定存在答案。求 ans 的过程。

核心：通过阅读题目，大致可以感受到一种贪心算法：从最左端开始，每隔一个单位距离 x 就安置一头牛，一定是能安置就安置，可以证明安置了就一定比不安置更优，最后统计安置了几头牛即可。

注意折半查找的边界，是k>=m还是k>m，看题目希望什么，题目希望ans尽可能的大，所以应该是 二分查找右边界，等于的时候优先去右边

代码:

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

#define INF 1e9
int a[100005],n,m;
bool check(int dis){
	int k=0,last=-INF;
	//k记录入住隔间的牛数量,last记录上一头牛的位置 
	for(int i=1;i<=n;i++)
		if(a[i]-last>=dis){//能安置就安置 
			last = a[i]; 
			k++;
		}
	return k>=m;	
    //如果k>=m说明入住的牛多了，这个解ans小了，要向右查找	
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>a[i];
		
	sort(a+1,a+n+1);//从小大快排 
	
	//二分答案的标准模版 
	int l=0,r=INF,ans,mid;
	while(l<=r){
		mid = (l + r)/2;
		if(check(mid)){
			ans=mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	cout<<ans;
	return 0;
}

习题1：洛谷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
#include <bits/stdc++.h> 
using namespace std;

int n,m,a[100005];
bool check(int len){
	int k=0;
	for(int i=1;i<=n;i++)
		k += a[i]/len;
	return k>=m;
    //如果k>=m说明小木头段多了，这个解ans小了，要向右查找	
}
int main(){
	cin>>n>>m;
	int maxlen=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		maxlen=max(a[i],maxlen);
	}
	
	int ans,l=1,r=maxlen;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			ans=mid;
			l = mid + 1;
		}
		else
			r = mid - 1;
	}
	cout<<ans;
	return 0;
}

这里用maxlen不用INF是我们可以判断出ans的大小不会超过maxlen，其实上题也是可以用这种方法的，但是在对数函数log的作用下，影响不大。

习题2：洛谷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
#include <bits/stdc++.h> 
using namespace std;

int n,m,a[50005],len;
bool check(int dis){
	int k=0;//移走的石头数量
	int nowpos=0;//现在的位置距离
	for(int i=1;i<=n+1;i++){
		if(a[i]-nowpos<dis)
			k++;
		else
			nowpos=a[i];	
	} 
	return k<=m;
	//如果k<=m说明移走的石头少了，留下的石头多了，这个解ans就偏小了，向右查找 
}
int main(){
	cin>>len>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	a[n+1]=len;//把终点石头加入数组，好算距离 
	int l=1,ans,r=len;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)){
			ans=mid;
			l = mid + 1;//向右查找 
		}
		else
			r = mid - 1;	
	}
	
	cout<<ans;
	return 0;
}