题解 P3132 【[USACO16JAN]愤怒的奶牛Angry Cows】

· · 题解

样例输入

5
8 10 3 11 1

样例输出

3.0

先是一些碎碎念

我的思路实际上有点繁琐，我看其他ac巨佬的代码都是1kb以下，我的直接1.5kb+了。然而他们都不愿意写题解（我写这篇题解的时候这题的题解库还是空无一物），所以我斗胆把自己的想法发上来了。

先看数据

n最大可达50000，一般会向O(nlogn)的复杂度思考，所以我们考虑进行二分。

从二分开始入手

所以我们先用f[i]记录以i为以i为圆心可以向左覆盖前i-1个点的最小半径。 再用g[i]记录以i为圆心可以向右覆盖至第n个点的最小半径。

根据贪心原理，假设第i个草堆处在某一次爆炸的左边界，则爆炸范围的右边界可以覆盖更远的范围，那么这次爆炸向右传递的最小半径必然比第i个草堆在左边界内的向右传递的最小半径不大。

那么我们二分枚举第一次爆炸的半径r。

枚举i，即第i个草堆为这次爆炸的左边界，再在左边界到右边界的草堆中枚举j，如果f[i]+1<=r并且g[i]+1<=r，则说明这个方案可行。

bool check(double x)
{
    for(int i=n;i>=1;i--)
    {
        if(f[i]+1<=x)
        {
            for(int j=i;j<=n&&a[j]<=a[i]+2.0*x;j++)
                if(g[j]+1<=x) return true;
            break;
        }
    }
    return false;
}

其实，真正的麻烦处，在预处理

我们要对f[i]和g[i]进行预处理

O(n2)复杂下的预处理如下

for(int i=2;i<=n;i++)
    {
        f[i]=999999999;
        for(int j=i;j>=1;j--)
        {
            f[i]=min(f[i],max(a[i]-a[j-1],f[j-1]+1));
            if(f[j-1]+1<a[i]-a[j-1]) break;
        }
    }
    for(int i=n-1;i>=1;i--)
    {
        g[i]=9999999999;
        for(int j=i;j<n;j++)
        {
            g[i]=min(g[i],max(a[j+1]-a[i],g[j+1]+1));
            if(g[j+1]+1<a[j+1]-a[i]) break;
        }
    }

在这段预处理中，a[i]-a[j-1]随j的增加而递减，而f[j-1]随j的增加而递增，所以这次max(a[i]-a[j-1],f[j-1]+1)一定在a[i]-a[j-1]和f[j-1]大小交界处取得，所以达到这个边界时可以break退出。

但这个O(n2)预处理加上边界判断也远远不能满足50000的数据。

既然要找边界，而且这个边界的判断有单调性，那么我们把枚举j的过程改成二分

for(int i=2;i<=n;i++)
    {
        f[i]=999999999;
        int l=1,r=i;
        while(l+1<r)
        {
            int mid=(l+r)/2;
            if(f[mid-1]+1<a[i]-a[mid-1]) l=mid;
            else r=mid;
        }
        f[i]=min(max(a[i]-a[l-1],f[l-1]+1),max(a[i]-a[r-1],f[r-1]+1));
    }
    for(int i=n-1;i>=1;i--)
    {
        g[i]=9999999999;
        int l=i,r=n-1;
        while(l+1<r)
        {
            int mid=(l+r)/2;
            if(g[mid+1]+1<a[mid+1]-a[i]) r=mid;
            else l=mid;
        }
        g[i]=min(max(a[l+1]-a[i],g[l+1]+1),max(a[r+1]-a[i],g[r+1]+1));
    }

因为我们要找边界处的数据进行处理，所以我们将条件置为l+1<r，保证l在边界处左侧，r在边界处右侧。

大体的思路就是这样吧

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c<='9'&&c>='0')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}

int n;
double a[50005];
double ans;
double eps=0.001;
double f[50005],g[50005];

void pre()
{
    f[1]=g[n]=0;
    for(int i=2;i<=n;i++)
    {
        f[i]=999999999;
        int l=1,r=i;
        while(l+1<r)
        {
            int mid=(l+r)/2;
            if(f[mid-1]+1<a[i]-a[mid-1]) l=mid;
            else r=mid;
        }
        f[i]=min(max(a[i]-a[l-1],f[l-1]+1),max(a[i]-a[r-1],f[r-1]+1));
    }
    for(int i=n-1;i>=1;i--)
    {
        g[i]=9999999999;
        int l=i,r=n-1;
        while(l+1<r)
        {
            int mid=(l+r)/2;
            if(g[mid+1]+1<a[mid+1]-a[i]) r=mid;
            else l=mid;
        }
        g[i]=min(max(a[l+1]-a[i],g[l+1]+1),max(a[r+1]-a[i],g[r+1]+1));
    }
} 

bool check(double x)
{
    for(int i=n;i>=1;i--)
    {
        if(f[i]+1<=x)
        {
            for(int j=i;j<=n&&a[j]<=a[i]+2.0*x;j++)
                if(g[j]+1<=x) return true;
            break;
        }
    }
    return false;
}

void solve()
{
    double l=1.0,r=a[n]*1.0;
    while(eps<r-l)
    {
        double mid=(l+r)/2.0;
        if(check(mid)) r=mid;
        else l=mid;
    }
    ans=l;
}

int main()
{
    freopen("angrycow.txt","r",stdin);
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read();
    sort(a+1,a+1+n);
    pre();
    solve();
    printf("%.1f",ans);
    return 0;
}