题目描述
blablabla
样例
blablabla
算法1
(二分套二分) $O(n\log n)$
在check的时候通过二分来查找可以减小常数,虽然排序已经有$O(n\log n)$了
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
const double eps=1e-6;
typedef long long ll;
int n;
double x[N];
bool check(double k)
{
double now=x[1]+k+k;
auto it=upper_bound(x+1,x+n+1,now+1e-6);
if(it==x+n+1)return 1;
now=(*it)+k+k;
it=upper_bound(x+1,x+n+1,now+1e-6);
if(it==x+n+1)return 1;
now=(*it)+k+k;
it=upper_bound(x+1,x+n+1,now+1e-6);
if(it==x+n+1)return 1;
return 0;
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>x[i];
sort(x+1,x+n+1);
double l=0,r=2e9,mid;
while(r-l>eps)
{
mid=(l+r)/2.0;
if(check(mid))r=mid;
else l=mid;
}
printf("%.6lf\n",r);
double now=x[1]+r;int cnt=2;
printf("%.6lf ",now);
for(int i=2;i<=n;i++)
if(x[i]>now+r+1e-6)
now=x[i]+r,cnt--,printf("%.6lf ",now);
while(cnt--)printf("%.6lf ",now);
return 0;
}