比赛 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;
}