王老师_二分查找+二分答案复习

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, a[N];
//a数组是有序的
二分查找的核心思想：用双指针选取一段范围，
然后我们会在这段范围里面寻找最好的答案，
我们每次把范围的中间值和目标值做比较，进行范围的缩小
二分查找 特快
二分查找的特点：思想非常好理解，但是代码细节比较多 + 题型也稍多
//1. 在有序a数组里面查找某个数字有没有出现过
bool erfen1(int x){
	int l = 1, r = n;
	while (l <= r){//一定写的是 l<=r
		int mid = (l + r) / 2;
		if (a[mid] == x) return 1;
		if (a[mid] > x) r = mid - 1;
		if (a[mid] < x) l = mid + 1;
	}
	return 0;
}
6-- > 1 2 2 2 2 4
//2. 在有序a数组里面查找某个数字第一次出现的位置，如果找不到 返回-1
int erfen2(int x){
	int l = 1, r = n, ans =-1;
	while (l <= r){//一定写的是 l<=r
		int mid = (l + r) / 2;
		if (a[mid] == x) ans = mid, r = mid - 1;
		if (a[mid] > x) r = mid - 1;
		if (a[mid] < x) l = mid + 1;
	}
	return ans;
}
//3. 在有序a数组里面查找某个数字最后一次出现的位置，如果找不到 返回-1
int erfen3(int x){
	int l = 1, r = n, ans =-1;
	while (l <= r){//一定写的是 l<=r
		int mid = (l + r) / 2;
		if (a[mid] == x) ans = mid, l = mid + 1;
		if (a[mid] > x) r = mid - 1;
		if (a[mid] < x) l = mid + 1;
	}
	return ans;
}
//结合第二类题型和第三类题型 我们可以快速的计算 某个数字在a数组里面的出现次数
//4.查找大于x的第一个位置,如果没找到返回 -1
int erfen4(int x){
	int l = 1, r = n, ans =-1;
	while (l <= r){
		int mid = (l + r) / 2;
		if (a[mid] > x) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	return ans;
}
//作用：查找大于x的数据有几个
//5.查找大于等于x的第一个位置,如果没找到返回 -1
int erfen5(int x){
	int l = 1, r = n, ans =-1;
	while (l <= r){
		int mid = (l + r) / 2;
		if (a[mid] >= x) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	return ans;
}
//作用：查找大于等于x的数据有几个
//6.查找小于x的最后一个位置，如果没找到 返回-1
int erfen6(int x){
	int l = 1, r = n, ans =-1;
	while (l <= r){
		int mid = (l + r) / 2;
		if (a[mid] < x) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}//作用：查找小于x的数据有多少个
//7.查找小于等于x的最后一个位置，如果没找到 返回-1
int erfen7(int x){
	int l = 1, r = n, ans =-1;
	while (l <= r){
		int mid = (l + r) / 2;
		if (a[mid] <= x) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	return ans;
}//作用：查找小于等于x的数据有多少个
//组合技：
int main(){

	return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
//每棵树的高度是在  1到1e9
//答案的范围是在？？？ 0 到 1e9 
// 我们要在答案的范围内 找到一个最优的答案
// 0 1 2 3 4 5 6 --  5e8 ---  1e9
long long a[N],n,m;
bool check(int x){//检测 砍伐高度为x的时候是否可行 可行的话返回1 不可行返回0
    int ans=0;
    for(int i=1;i<=n;i++){
        if(a[i]>x){
            ans+=a[i]-x;
        }
    }
    if(ans>=m) return 1;
    else return 0;
}
signed main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    int l=0,r=1e9,ans=-1;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid)==1){
            ans=mid;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    cout<<ans;
    return 0;
}