糖果传递问题

今天接触到这道水题，才发现……我好菜啊T^T
废话少说，革命尚未成功，同志们还需努力啊！
这道题用到了前缀和、归纳法、贪心思想。
看到题我们可以马上想到求平均值，之后嘛……
一个一个数呗（he~tui）T^T进入正题。

分析

首先设x[i]表示i+1向i传的糖果数（可以为正也可以为负），特殊的x[n]表示1向n传递的糖果数

我们用数组储存下数据a[i],求得平均值为a。
我们可以得到：
a[1]+x[1]-x[n]=a（这个式子是第一个孩子加上第二个孩子给的糖果减去给第n个孩子的糖果就是平均值）
a[2]+x[2]-x[1]=a
……
a[n-1]+x[n-1]-x[n-2]=a
a[n]+x[n]-x[n-1]=a（其实这个式子是没用的）
既然要求最少的传递的次数，就相当于：ans=x[1]+x[2]+x[3]……+x[n];
x[1]=a-a[1]+x[n]
x[2]=a-a[2]+x[1]=2*a-a[2]-a[1]+x[n]
…
x[n-1]=a-a[n-1]+x[n-2]=(n-1)a-a[n-1]-a[n-2]…-a[1]+x[n];
设s[i]=(a[1]+a[2]…+a[i])-ia;所以x[i]=s[i]-x[n];
这是我们还有一个未知数x[n];那它又有什么用呢？别急接着看；
ans=|x[1]|+|x[2]|+…+|x[n]|=(s[1]-x[n])+(s[2]-x[n])…+(s[n]-x[n]);
既然是求最小值那就相当于在数轴上有n个点，当x[n]是多少时最小，当然是中位数的时候了。
求出s[i]的中位数，当x[n]为中位数时，最小。

代码

#include<bits/stdc++.h>
using namespace std;
long long int a[1000005],s[1000005];
int  main()
{
	long long int n,i,sum=0,ans=0,mid;
	scanf("%lld",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	sum/=n;
	for(i=1;i<=n;i++)
		s[i]=s[i-1]+sum-a[i];
	sort(s+1,s+n+1);
	mid=s[(n+1)/2];
	for(i=1;i<=n;i++)
		ans+=abs(s[i]-mid);
	printf("%lldn",ans);
	return 0;
}

最后

以上就是单薄衬衫为你收集整理的糖果传递问题的全部内容，希望文章能够帮你解决糖果传递问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。