P1677 [USACO18FEB] Hoofball B题解

· · 题解

题目链接

思路

由于奶牛只会传球给离它最近的奶牛，可以想到将每个奶牛的位置进行从小到大排序，那么问题就变为奶牛传球给左右距离它近的奶牛，只需要考虑两边。

接下来，可以模拟一遍每个奶牛得到球后会传给哪个奶牛，每个奶牛传给球的奶牛的位置记在 to 数组中，每个奶牛从其他奶牛传球能得到球的次数记在 cnt 数组中。很显然，cnt 值为 0 的奶牛不能从其他奶牛传球中得到球，记录这些奶牛的个数为 ans。

注意：两个奶牛相互传球且这两个奶牛都不能从其他奶牛中得到球时，答案也需要加 1。

INF 不能设置为 2147483647，在计算距离时会超出 int 范围。

代码

#include<bits/stdc++.h>
using namespace std;
#define INF 2000000000
const int N=105;
int n,ans;
int a[N],to[N],cnt[N];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);//将奶牛按距离左边从小到大排序 
    a[0]=-INF; a[n+1]=INF;
    for(int i=1;i<=n;i++)
        if(a[i]-a[i-1]>a[i+1]-a[i])//因为距离相同传给距左边最远的奶牛，那么只能用'小于'
        {
            to[i]=i+1;
            cnt[i+1]++;
        }else{
            to[i]=i-1;
            cnt[i-1]++;
        }
    //求出每个点的奶牛接到求后会传球给的奶牛

    for(int i=1;i<=n;i++)
        if(!cnt[i]) ans++;
    //如果不能通过传球得到球，那么ans+1 

    for(int i=1;i<=n;i++)
        if(cnt[i]==1&&cnt[i+1]==1&&to[i]==i+1&&to[i+1]==i)
            ans++;
    //如果两个奶牛是相互传球，且其他奶牛不会传球给这两个奶牛，那么ans也要加1 

    printf("%d\n",ans);
    return 0;
}