基础二分路由器放置WA10分

常规
1 
#include<iostream>
#include<algorithm>
using namespace std;
int m,n,a[100005];
bool check(double x){
	int t=a[1];
	int sum=0;
	for(int i=2;i<=n;i++){
		if(a[i]>t){
			t=a[i]+x*2-1;
			sum++;
		}
	}
	return sum<=m;
}
bool cmp(int a,int b){
	return a<b;
}
int main(){
	cin>>m>>n;
	int maxx=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		maxx=max(maxx,a[i]);
	}
	sort(a+1,a+n+1,cmp);
	double l=1,r=maxx;
	while(l<r){
		double mid=(l+r)/2;
		if(check(mid)){
			r=mid;
		}
		else{
			l=mid+1;
		}
	}
	printf("%.1f",l);
	return 0;
}
1 个赞
2 
#include<bits/stdc++.h>
using namespace std;
long long n,m,a[100001];
bool f(double x){
	double ans=0,cnt=a[1]+2*x;
	for(int i=2;i<=n;i++){
		if(a[i]>cnt){
			ans++;
			cnt=a[i]+2*x;
		}
	}
	return ans<m;
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	double l=0.01,r=a[n];
	while(l+0.01<r){
		double mid=(l+r)/2;
		if(f(mid)){
			r=mid;
		}else{
			l=mid+0.01;
		}
	}
	printf("%.1lf",r);
}

有不懂私我

2 个赞
3

谢谢，问题解决了

1 个赞