? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 950K 糖果传递
?
题目描述
有n个小朋友坐成一圈，每人有aia_iai?颗糖果。每人只能给左右两人传递糖果。每人每次传递一颗糖果的代价为1。求使所有人获得均等糖果的最小代价。
输入描述:
第一行有一个整数n，表示小朋友个数；
在接下来n行中，每行一个整数aia_iai?。
输出描述:
输出使所有人获得均等糖果的最小代价。
示例1
输入
4 1 2 5 4
输出
4
备注:
对于30%的数据，n≤1000； 对于100%的数据，n≤ 10^6，保证答案可以用64位有符号整数存储。
完整代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<sstream>
using namespace std;
int main()
{
int n;
cin>>n;
long long a[n];
long long x;
long long b[n];
long long min=0;
long long sum[n];//sum[1]=a[1];sum[2]=a[1]+a[2];方便计算b[n];
for(int i=0;i<n;i++)
cin>>a[i];
sum[0]=0;
for(int i=1;i<n;i++)
sum[i]=sum[i-1]+a[i];
int adv=(sum[n-1]+a[0])/n;//平均值
for(int i=1;i<n;i++)
b[i]=sum[i]-i*adv;//根据数学推导出来
sort(b+1,b+n);
x=b[n/2];//求b[n]中位数
min=abs(x);
for(int j=1;j<n;j++)
{
min=min+abs(x-b[j]);
}
printf("%lld\n",min);
return 0;
}分析过程：
该题使用贪心算法+数学推导，数学推导为关键。
?
写得比较潦草（字丑，没得办法）也是自己解题时的一个草稿，有参考价值的话，可以看看，如果有看不懂的地方可以评论提出，一定会回复的。
分享自己做题的一些方法，也算是对自己代码之路的记录。一名大三的编程小学生，性别女，可以进行交流，一起进步。
之后会持续分享关于牛客网的题库及解题思路，以及一些的代码网站的介绍，有不知道自己怎么去提高算法能力，怎么去选择网站的可以持续关注。（我只是小白）
?