比赛 |
4043级NOIP2022欢乐赛7th |
评测结果 |
AAAAAAAAAA |
题目名称 |
愤怒的奶牛 |
最终得分 |
100 |
用户昵称 |
nick |
运行时间 |
0.155 s |
代码语言 |
C++ |
内存使用 |
4.28 MiB |
提交时间 |
2022-11-20 11:55:40 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
int n,x[100005];
bool check(int r)
{
int minn=0;
int maxn=1;
int en=1,st=1;
for(int i=1;i<=n;i++)
{
minn+=2;
if(i==n)return true;
if(minn+2>r){en=i;break;}
if(x[i+1]-x[i]>minn){
minn=x[i+1]-x[i];
}
if(minn>=r){en=i;break;}
maxn=i;
while(maxn<n&&x[maxn+1]-x[i]<=minn)
maxn++;
i=maxn-1;
}
if(en==n)return true;
st=en;
while(st<n&&x[st+1]-x[en]<=2*r)
st++;
if(st==en)return false;
minn=r;
maxn=st;
for(int i=st;i<=n;i++)
{
minn-=2;
if(i==n)return true;
if(x[i+1]-x[i]>minn)return false;
while(maxn<n&&x[maxn+1]-x[i]<=minn)
maxn++;
i=maxn-1;
}
return true;
}
long long erfen(long long l,long long r)
{
if(l==r)return l;
long long mid=(l+r)/2;
if(check(mid))return erfen(l,mid);
else return erfen(mid+1,r);
}
int main()
{
freopen("angry.in","r",stdin);
freopen("angry.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
cin>>x[i],x[i]*=2;
sort(x+1,x+1+n);
long long ans=erfen(0,x[n]);
if(ans%2)printf("%lld.5\n",ans/2);
else printf("%lld.0\n",ans/2);
return 0;
}