二分查找和二分答案

1.查找

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int n, m;

int main(){
	cin>>n>>m;
	for(int i = 1; i <= n; i++) cin>>a[i];
	int k;
	while(m--){
		cin>>k;
		int res = lower_bound(a + 1, a + n + 1, k) - a;
		if(a[res] != k) cout<<-1<<" ";
		else cout<<res<<" ";
	}
	return 0;
}

2.A-B 数对

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
int q[N];
int n, c;

int main(){
	cin>>n>>c;
	for(int i = 1; i <= n; i++) cin>>q[i];
	sort(q + 1, q + n + 1);
	long long ans = 0;
	for(int i = 1; i <= n; i++){
		int b = q[i] - c;
		int res1 = lower_bound(q + 1, q + n + 1, b) - q;
		int res2 = upper_bound(q + 1, q + n + 1, b) - q - 1;
		//cout<<b<<" "<<res1<<" "<<res2<<endl;
		if(q[res1] == b && q[res2] == b) ans += res2 - res1 + 1;
	}
	cout<<ans;
	return 0;
}

3.砍树

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e6 + 10;
int q[N];
int n, m;

int check(int x){
	long long sum = 0;
	for(int i = 1; i <= n; i++){
		if(q[i] > x) sum += q[i] - x;
	}
	return sum < m;
}

int main(){
	cin>>n>>m;
	for(int i = 1; i <= n; i++) cin>>q[i];
	int l = -1, r = 2e9 + 1;
	while(l + 1 < r){
		int mid = (l + r) / 2;
		if(check(mid)) r = mid;
		else l = mid;
	}
	cout<<l;
	return 0;
}

4.一元三次方程求解

#include<iostream>
#include<algorithm>
using namespace std;
double a, b, c, d;

double check(double x){
	double sum = a * x * x * x + b * x * x + c * x + d;
	return sum;
}

int main(){
	cin>>a>>b>>c>>d;
	int f = 0;
	for(int i = -100; i <= 100; i++){
		if(f == 3) break;
		double l = i - 0.5, r = i + 0.5;
		if(check(l) * check(r) <= 0){
			if(check(l) >= 0){
				while(l + 0.00001 < r){
					double mid = (l + r) / 2;
					if(check(mid) > 0) l = mid;
					else r = mid; 
				}
			}else if(check(l) < 0){
				while(l + 0.00001 < r){
					double mid = (l + r) / 2;
					if(check(mid) < 0) l = mid;
					else r = mid; 
				}
			}
			f++;
			printf("%.2lf ", r);
		}
	}
	return 0;
}

5.烦恼的高考志愿

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int m, n;

int main(){
	cin>>m>>n;
	for(int i = 1; i <= m; i++) cin>>a[i];
	sort(a + 1, a + m + 1);
	long long ans = 0, x;
	for(int i = 1; i <= n; i++){
		cin>>x;
		int l = 0, r = m + 1;
		while(l + 1 < r){
			int mid = (l + r) / 2;
			if(a[mid] < x) l = mid;
			else r = mid;
		}
		//cout<<l<<" "<<r<<endl;
		if(x < a[1]) ans += a[1] - x;
		else ans += min(abs(x - a[l]), abs(x - a[r]));
	}
	cout<<ans;
	return 0;
}

6.木材加工

无解的时候，可以取到左边界 l

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int n, k;

int check(int x){
	long long cnt = 0;
	for(int i = 1; i <= n; i++){
		cnt += a[i] / x;
	}
	return cnt < k;
}

int main(){
	cin>>n>>k;
	for(int i = 1; i <= n; i++) cin>>a[i];
	int l = 0, r = 1e8 + 1;
	while(l + 1 < r){
		int mid = (l + r) / 2;
		if(check(mid)) r = mid;
		else l = mid;
	}
	cout<<l;
	return 0; 
}

7.跳石头

二分最短跳远距离的最大长度

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 5e4 + 10;
int a[N];
int len, n, m;

int main(){
	cin>>len>>n>>m;
	int t = 0, x;
	for(int i = 1; i <= n; i++){
		cin>>x;
		a[i] = x - t;
		t = x;
	}
	a[n + 1] = len - t;
	//for(int i = 1; i <= n + 1; i++) cout<<a[i]<<" ";
	if(n == m){
		cout<<len;
	}else{
		int l = 0, r = len / (n - m) - 1;
		while(l + 1 < r){
			int mid = (l + r) / 2;
			int cnt = 0, res = 0;;
			for(int i = 1; i <= n + 1; i++){
				res = a[i];
				while(res < mid && i <= n){
					cnt++;
					res += a[++i];
				}
			}
			if(cnt <= m) l = mid;
			else r = mid;
		}
		cout<<l;
	}
	return 0; 
}

8.路标设置

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int len, n, k;

int main(){
	cin>>len>>n>>k;
	int x, t = 0;
	for(int i = 1; i <= n; i++){
		cin>>x;
		a[i] = x - t;
		t = x;
	}
	a[n + 1] = len - t;
	int l = 0, r = len;
	while(l + 1 < r){
		int mid = (l + r) / 2;
		int cnt = 0, res;
		for(int i = 1; i <= n + 1; i++){
			res = a[i];
			while(res > mid){
				cnt++;
				res -= mid;
			}
		}
		if(cnt <= k) r = mid;
		else l = mid;
	}
	cout<<r;
	return 0;
}

9.数列分段

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, m;

int main(){
	cin>>n>>m;
	int l = 0, r = 0;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
		l = max(l, a[i]);
		r += a[i];
	}
	l--, r++;
	while(l + 1 < r){
		int mid = (l + r) / 2;
		int res, cnt = 0;
		for(int i = 1; i <= n; i++){
			res = a[i];
			cnt++;
			while(res + a[i + 1] <= mid && i < n){
				res += a[++i];
			}
		}
		if(cnt <= m) r = mid;
		else l = mid;
	}
	cout<<r;
	return 0;
}

10.银行贷款

#include<iostream>
#include<cmath>
using namespace std;
int a, b, c;

double check(double x){
	double res = a;
	for(int i = 1; i <= c; i++){
		res = res * (1 + x) - b;
	}
	return res;
}

int main(){
	cin>>a>>b>>c;
	double l = 0, r = 3, ans;
	while(l + 0.00001 < r){
		double mid = (l + r) / 2;
		if(check(mid) > 0) r = mid;
		else if(check(mid) < 0) l = mid;
		else{
			ans = mid * 100;
			break;
		}
		ans = mid * 100;
	}
	printf("%.1lf", ans);
	return 0;
}

11.小鸟的设备

二分可以使用的时间，边界一定要取到 [0, 1e10]

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, p;

int check(double x){
	double res = 0;
	for(int i = 1; i <= n; i++){
		double t = b[i] - a[i] * x;
		if(t < 0) res += -t;
		if(res > x * p) return 0; 
	}
	return 1;
}

int main(){
	cin>>n>>p;
	for(int i = 1; i <= n; i++) cin>>a[i]>>b[i];
	double l = 0, r = 1e10;
	while(l + 0.00001 < r){
		double mid = (l + r) / 2;
		if(check(mid)) l = mid;
		else r = mid;
	}
	if(r >= 1e10) cout<<-1;
	else printf("%.10lf", l);
	return 0;
}