题目链接

思路

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

接下来，可以模拟一遍每个奶牛得到球后会传给哪个奶牛，每个奶牛传给球的奶牛的位置记在 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;
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 500005;
int n, a[maxn], Du[maxn], ans, cnt, nxt[maxn];
bool vis[maxn];

void DFS(int x) {
    if (vis[x]) return;
    vis[x] = 1;
    DFS(nxt[x]);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++) {
        if (i == 1) Du[i + 1]++, nxt[i] = i + 1;
        else if (i == n) Du[i - 1]++, nxt[i] = i - 1;
        else {
            if (a[i] - a[i - 1] <= a[i + 1] - a[i]) Du[i - 1]++, nxt[i] = i - 1;
            else Du[i + 1]++, nxt[i] = i + 1;
        }
    }
    for (int i = 1; i <= n; i++) if (!Du[i]) ans++, DFS(i);
    for (int i = 1; i <= n; i++) if (!vis[i]) cnt++;
    printf("%d", ans + cnt /