比赛 |
4043级NOIP2022欢乐赛7th |
评测结果 |
AWAWAAAAWA |
题目名称 |
愤怒的奶牛 |
最终得分 |
70 |
用户昵称 |
yrtiop |
运行时间 |
1.235 s |
代码语言 |
C++ |
内存使用 |
4.81 MiB |
提交时间 |
2022-11-20 10:35:29 |
显示代码纯文本
#include <bits/stdc++.h>
const double eps = 1e-3;
const int maxn = 5e4 + 5;
int n;
double a[maxn],pre[maxn],suf[maxn];
bool check(double k) {
for(int i = 1;i <= n;++ i) {
int r = std::upper_bound(a + 1 , a + 1 + n , a[i] + 2.0 * k) - a - 1;
if(pre[i] <= k - 1&&suf[i] <= k - 1)return true;
}
for(int i = n;i;-- i) {
int r = std::lower_bound(a + 1 , a + 1 + n , a[i] - 2.0 * k) - a;
if(pre[r] <= k - 1&&suf[i] <= k - 1)return true;
}
return false;
}
int main() {
freopen("angry.in","r",stdin);
freopen("angry.out","w",stdout);
scanf("%d",&n);
for(int i = 1;i <= n;++ i)
scanf("%lf",&a[i]);
std::sort(a + 1 , a + 1 + n);
pre[1] = 0;
for(int i = 2;i <= n;++ i) {
pre[i] = 1e9;
double l = a[i] - a[i - 1],r = 1e9;
while(r - l > eps) {
double mid = (l + r) / 2.0;
int k = std::lower_bound(a + 1 , a + 1 + n , a[i] - mid) - a;
if(pre[k] <= mid - 1)r = mid;
else l = mid;
}
pre[i] = r;
}
suf[n] = 0;
for(int i = n - 1;i;-- i) {
suf[i] = 1e9;
double l = a[i + 1] - a[i],r = 1e9;
while(r - l > eps) {
double mid = (l + r) / 2.0;
int k = std::upper_bound(a + 1 , a + 1 + n , a[i] + mid) - a - 1;
if(suf[k] <= mid - 1)r = mid;
else l = mid;
}
suf[i] = r;
}
double l = 0,r = 1e9;
while((r - l) > eps) {
double mid = (l + r) / 2.0;
if(check(mid))r = mid;
else l = mid;
}
printf("%.1lf\n",l);
return 0;
}