二分查找与二分答案

作业介绍

/*
有序
1 2 3 3 3 4 4 4 5 5 5 5
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int n,a[N],q;
int main(){
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=q;i++){
		int x;
		cin>>x;
		int l=1,r=n;
		int ans = -1;
		while(l<=r){
			int mid = (l+r)/2;
			if(a[mid]<x){
				l = mid+1;
			}
			else if(a[mid]==x){
				ans = mid;
				r = mid-1;
			}
			else if(a[mid]>x){
				r = mid-1;
			}
		}
		cout<<ans<<" ";
	}
	return 0;
}
/*
A
B = A-c
枚举第一个B的位置  d
枚举第一个大于B的位置  e
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int n,a[N],A,B,c;
int find1(int x){
	//返回第一个大于等于x的下标
	int l=1,r=n,res=0;
	while(l<=r){
		int mid = (l+r)/2;
		if(a[mid]>=x){
			res = mid;
			r = mid-1;
		}
		else l=mid+1;
	}
	return res;
}
int find2(int x){
	//返回第一个大于x 的下标
	int l=1,r=n,res=0;
	while(l<=r){
		int mid = (l+r)/2;
		if(a[mid]>x){
			res = mid;
			r = mid-1;
		}
		else l = mid+1;
	}
	return res;
}
int main(){
	cin>>n>>c;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	long long res = 0;
	for(int i=1;i<=n;i++){
		int A = a[i],B=A-c;
		res+=find2(B)-find1(B);
	}
	cout<<res<<endl;
	return 0;
}
/*
枚举举例x 判断举例x能否放下所有的牛
如果能放下,比x大一点
如果放不下,比x小一点
*/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,a[N],m;
int check(int x){
	int now = a[1];
	int cnt = 1;
	for(int i=2;i<=n;i++){
		if(a[i]-now>=x){
			now = a[i];
			cnt++;
		}
	}
	if(cnt>=m)return 1;
	else return 0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	int l=1,r=1000000000,res=-1;
	while(l<=r){
		int mid = (l+r)/2;
		if(check(mid)){
			res = mid;
			l = mid+1;
		}
		else r = mid-1;
	}
	cout<<res<<endl;
	return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
int n,k;
int a[N];
int check(int x){
	//每一段切成x,能否切够k段
	int cnt = 0;
	for(int i=1;i<=n;i++){
		cnt+=a[i]/x;
	}
	if(cnt>=k)return 1;
	else return 0;
}
int main(){
	cin>>n>>k;
	long long sum = 0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	if(sum<k){
		cout<<0<<endl;
		return 0;
	}
	int l=1,r=100000000,res=-1;
	while(l<=r){
		int mid = (l+r)/2;
		if(check(mid)){
			res = mid;
			l = mid+1;
		}
		else r= mid-1;
	}
	cout<<res<<endl;
	return 0;
}

题目

认领作业后才可以查看作业内容。
状态
正在进行…
题目
13
开始时间
2026-4-19 0:00
截止时间
2026-6-30 23:59
可延期
24 小时