自动搬运

查看原文

来自洛谷，原作者为

	Silent1019 这家伙很勤快，什么都留下了

搬运于2025-08-24 21:27:49，当前版本为作者最后更新于2024-02-05 22:33:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

思路

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

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