糖果传递
有n个小朋友坐成一圈,每人有a[i]个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为1。
求使所有人获得均等糖果的最小代价。
输入格式
第一行输入一个正整数n,表示小朋友的个数。
接下来n行,每行一个整数a[i],表示第i个小朋友初始得到的糖果的颗数。
输出格式
输出一个整数,表示最小代价。
[HTML_REMOVED]
数据范围
1≤n≤1000000
数据保证一定有解。
输入样例
4
1
2
5
4
输出样例
4
算法/复杂度
据说是贪心的经典题目,背背模板吧,hhhhh
思路:
- 题目默认每次只能给左边的人或者右边的人。同样, 最优解一定是没有来回的。所以,全局来看,两个小朋友间的给予关系,可以用一条单向线表示。
- 为了让每个人的糖果分的一样多,那么x1, x2 ,x3.....的取值就是这样子的
- 然后根据数学原理 X1 取 A B C D E 的中位数,可令距离和最小。
(不懂的百度货仓选址问题)
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int a[1000010],p[1000010],x1,n;
ll ai =0,res = 0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
//cin>>a[i] 4806 ms
scanf("%d",&a[i]);//2320 ms
ai+=a[i];
}
//求平均值
ai/=n;
//求那几个推导出来的理论点
p[1] = 0;
for(int i = 2 ; i <= n; i++)
p[i] = p[i-1] + ai - a[i];
//取中位数
sort(p+1,p+n+1);
if(n%2==0) x1 = (p[n/2] + p[n/2+1])/2;
else x1 = p[n/2];
//求距离和
for(int i = 1 ; i <= n ; i++)
res += abs(x1 - p[i]);
cout<<res<<endl;
return 0;
}