二分答案-模板
2024-10-04 17:15:47
发布于:广东
47阅读
0回复
0点赞
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+10;
int n,c;
int p[N];
bool check(int x){
int sum = 1;//记录隔间数
int xf = p[1];//第一个隔间坐标
for(int i=2;i<=n;i++){//第二个开始
if(p[i]-xf>=x){//如果够间隔(mid)放第二个
sum++;//才累加
xf = p[i];//再去更新下一个隔间位置,找第三个、第四个.....
}
}
//return sum>=c;
if(sum>=c){
return 1;
}else{
return 0;
}
}
int main(){
cin>>n>>c;
for(int i=1;i<=n;i++){
cin>>p[i];
}
//二分前提是有序
sort(p+1,p+1+n);
//声明二分边界(最小、最大)
int l=1,r=p[n]-p[1];
int mid,ans=0;
//二分框架
while(l<=r){
//①求中间值
mid = (l+r)/2; //等价(l+r)>>1
//②拿mid 去 check
if(check(mid)){
ans = mid;
l = mid + 1;
}else{
r = mid - 1;
}
}
cout<<ans;//输出答案
return 0;
}
这里空空如也
有帮助,赞一个