二分题单

关于二分区间的操作

//左闭右闭
while(l<=r){
	mid = (l+r)>>1;
	if(check(mid)) l = mid+1;
	else r = mid - 1;
}
cout<<l;

//左闭右开
while(l<r){
	mid = (l+r)>>1;
	if(check(mid)) l = mid + 1;//if(nums[mid]<target)
	else r = mid;
}
cout<<l;
//注意check()的判断true应该是小于而不是小于等于

//左开右闭
while(l<r){
	mid = (l+1+r)>>1;
	if(check(mid)) r = mid -1;//if(nums[mid]>target)
	else l = mid;
}
cout<<L;
//注意对于check()的判断true应该是大于而不是大于等于

P1102 A-B数对

题目要求就是找出符合A - B = C的情况。

题解，我们可以知道C是已知的，所以我们可以写成A = B + C，这样让其中的b作为数组的元素之一，然后查找数组中有没有符合B+C的值。有的话就找到对应的值的长度。

STL中的upper_bound(begin,end,val)是找到对应数字的最后一个的下一个的地址,lower_bound(begin,end,val)返回的是第一个地址。

代码

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long ll;
constexpr int N = 2e5+10;
ll a[N];
void solve(){
	ll n,c;
	cin>>n>>c;
	for(int i = 0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	ll sum = 0;
	for(int i = 0;i<n;i++){
		sum += upper_bound(a,a+n,a[i]+c)-lower_bound(a,a+n,a[i]+c);
		//a[i]+c就是b，在元素找出符合a的值
	}
	cout<<sum;
}
int main(){
	solve();
}

P1873 砍树

题目大概意思就是说有一排数，然后我们需要找到最大的整数高度H，使他的切下来的木材至少为M米，也就是说我们需要找到最大值H，就是说我们需要二分的就是找到的右区间的值，就是左开右闭的二分区间。所以他的标准值就是m。所以我们二分的值就是木材的长度。

代码

#include<bits/stdc++.h>
const int N = 1e6+10;
typedef long long ll;
using namespace std;
ll n,m,l,r,trees[N];
void solve(){
	cin>>n>>m;
	for(int i = 1;i<=n;i++){
		cin>>trees[i];
		r = max(r,trees[i]);
	}
	while(l<r){//查找的右区间
		ll mid = (l+r+1)>>1;
		ll s = 0;
		for(int i = 1;i<=n;i++){
			if(trees[i]>mid){
				s += trees[i] - mid;//将多的部分切下来
			}
		}
		if(s>=m){//如果切的过多就是还要更高
			l = mid;
		
		else r = mid - 1;
	}
	cout<<l;
}
int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
	solve();
}

P1678 烦恼的高考志愿

题目的意思

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

输入格式

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

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

题解：就是说我们会有一组数组是学校的录取分数，还有一组就是学生的估分成绩，我们需要给学生推荐学校然后将两者的差的成绩算出来然后加给sum，找到就是不满意度和的最小值，所以就是查找二分的左区间就是用左区间的模板。由于不需要二分答案只需要二分查找，所以这里可以用二分的STL。

对于STL中如果值不是在数组里会返回什么样的东西。举个例子：在升序数组中，比如是[1,2,4,5]那么lower_bound(3),upper_bound(3)都返回的是下标2就是值是4,如果是upper_bound(2)返回的是下标2,lower_bound(2)返回的就是下标1。所以我们可以看出当找到的数不是数组中，那么lower_bound()就会返回第一个比要查询的值的大的值，如果比所有的数字大的话那么就是返回的end的地址。

题解

#include<bits/stdc++.h>
const int N = 1e6+10;
typedef long long ll;
using namespace std;
int x[N],s[N]; 
void solve(){
	int m,n;
	cin>>m>>n;
	for(int i = 1;i<=m;i++){
		cin>>x[i];
	}
	sort(x+1,x+1+m);
	for(int i = 1;i<=n;i++){
		cin>>s[i];
	}
	ll sum = 0;
	sort(s+1,s+1+n);
	for(int i = 1;i<=n;i++){
		int a = lower_bound(x+1,x+1+m,s[i])-x;
		if(a==1){//在开头
			sum+=abs(x[a]-s[i]);
		}
		else if(a==m+1){//在末尾
			sum += abs(x[m]-s[i]);
		}
		else{//中间的数
			sum += min(abs(x[a-1]-s[i]),abs(x[a]-s[i]));
		}
	}
	cout<<sum;
}
int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    solve();
}

P2440 木材加工

题目的大概意思就是将一群木头切割成k段长度均为l的小段木头，并且找出的是l的最大值，要求的都是整数，所以我们需要查找的右区间，所以用的是左开右闭的区间的二分模板

题解：就是我们的mid函数应该是木头的长度，然后check()函数就是判断能不能割成就是将木材的长度除以mid的个数，判断和要求的木材段数的关系。

代码

#include<bits/stdc++.h>
const int N = 1e5+10;
typedef long long ll;
using namespace std;
ll n,k,a[N];
ll l,r = 1e8+5;
bool f(ll x){
	ll ans = 0;
	for(int i = 1;i<=n;i++){
		ans += a[i]/x;
	}
	return ans>=k;
}
void solve(){
	cin>>n>>k;
	for(int i = 1;i<=n;i++){
		cin>>a[i];	
	}
	while(l<r){
		ll mid = (l+r+1)>>1;
		if(f(mid)){
			l = mid;
		}		
		else{
			r = mid -1 ;
		}
	}
	cout<<l;
	return;
}
int main(){
	std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    solve();
}

P2678 跳石头

题目：一年一度的“跳石头”比赛又要开始了！这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有N 块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。、

输入格式

第一行包含三个整数L,N,M，分别表示起点到终点的距离，起点和终点之间的岩石数，以及组委会至多移走的岩石数。保证 L≥1 且 N≥M≥0。接下来 N 行，每行一个整数，第i 行的整数Di​(0<Di​<L)， 表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出，且不会有两个岩石出现在同一个位置

输入输出样例

25 5 2 
2
11
14
17 
21

4

题解这里有个坑点就是最后一个岩石是终点，所以岩石的最终的总数是n+1，这个很坑，一开始没想到，然后一直wa，最后看题解才知道。然后我们找到的是最大值所以就是查找右边界的二分模板。然后check()函数里面应该判断的是当前假设的最短的跳跃距离所取走的石头数是不是可以<=至多移走的岩石数。

#include<bits/stdc++.h>
const int N = 5e5+10;
typedef long long ll;
using namespace std;
int a[N];
int d,n,m;
bool check(int x){
    int cnt = 0;//当前最短跳跃需要移走的个数
    int now = 0;
    int i = 0;
    while(i<n+1){
        i++;
        if(a[i]-a[now]<x){//如果跳跃距离小于当前的就需要移
            cnt++;
        }
        else{
            now = i;//如果不需要那就跳到当前的石头
        }
    }
    if(cnt>m) return false;//大于就说明小的更多还不够小



    else return true;
}
void solve(){
    cin>>d>>n>>m;
    for(int i = 1;i<=n;i++) cin>>a[i];
    a[n+1] = d;//相当于总数是n+1
    int l = 0,r = d;
    while(l<r){
        int mid = (l+r+1)>>1;
        if(check(mid)){
            l = mid;
        }
        else{
            r = mid-1;
        }
    }
    cout<<l;
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    solve();
}