2026年7月5日（ida*）--二分
2026-07-05 11:28:16
发布于：广东
3阅读
0回复
0点赞
//二分的前提，必须具有单调性（单调递增，或者单调递减都可以）
//1 2 3 4 5 6 7 //下标a[N]数组
//1 3 5 6 9 10 12//数据
int l=1,r=7;(查找的范围边界)
//目标找小于等于x的最大值
//x=5
int inx=0;//存储最终的答案
while(l<=r){
int mid=(l+r)/2;//取边界中间
if(a[mid]<=x){
inx=mid;//记录答案
l=mid+1;//跳过小的部分和重复的部分
}else{
r=mid-1;
}
}
cout<<a[inx]<<endl;
//x=5;
//1 2 3 4 5 6 7 //下标a[N]数组
//1 3 5 6 9 10 12//数据
//l=1,r=7;mid=4;
//a[4]=6 a[4]>x;r=mid-1=3;
//l=1,r=3; mid=2;
//a[2]=3 a[2]<=x; inx=mid=2（记录答案）l=mid+1=3;
//l=3,r=3;
//a[3]=5; a[3]<=x;inx=mid=3;
//100 50 50
//50 25 25
//25 12 13
//13 6 7
//7 3 4
//4 2 2
//2 1 1
lower_bound(a+1,a+n+1,x);第一个大于等于x的位置
upper_bound(a+1,a+n+1,x);第一个大于x的位置
//如何通过lower_bound或者upper_bound去查找大于等于x的位置
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
sort(a+1,a+n+1);
int q;
cin>>q;
while(q--){
int x;cin>>x;
cout<<upper_bound(a+1,a+n+1,x)-a<<endl;
}
}
https://www.acgo.cn/problemset/info/29698?homeworkId=21694&teamCode=1989649572886384640
//8 9 10 17 (木头长度)
//10 要求分割为10段
//1:8+9+10+17=44
//2:4+4+5+8=21
//3:2+3+3+5=13;
//4:2+2+2+4=10;
//5:1+1+2+3=7;
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
#define ll long long
ll a[N];
int n,k;
//check只求解单一情况下的结果
int check(int x){//当每段分割长度为x的时候分割出的总段数
ll sum=0;
for(int i=1;i<=n;i++){
sum+=a[i]/x;
}
return sum;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>a[i];
int l=1,r=1e9,ans=0;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)>=k){
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
cout<<ans<<endl;
}
这里空空如也
有帮助，赞一个