算法-贪心-122. 糖果传递
题目
有 n个小朋友坐成一圈，每人有 a[i]个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 1。
求使所有人获得均等糖果的最小代价。
输入格式
第一行输入一个正整数 n，表示小朋友的个数。
接下来 n 行，每行一个整数 a[i]，表示第 i 个小朋友初始得到的糖果的颗数。
输出格式
输出一个整数，表示最小代价。
数据范围
1≤n≤1000000,
0≤a[i]≤2×10的9次方,
数据保证一定有解。
输入样例：
4
1
2
5
4
输出样例：
4思路
- 糖果不会凭空增加或者消失；本题只考虑一定有解的情况，也就是总数一定能够整除n；不会出现环形给的情况：a->b->c->a;
- 数据范围是1e6,所以要做到nlogn或者是O(n)的情况;
- 建立数学模型：
- xi可正可负；
- 目标：使所有xi的绝对值相加之和最小
- 限制：
- n-1个独立的方程，n个未知数，可以用某一个的x来表示其他的x
- 目标函数转化为：（类似上一题的货物运输：求中位数+求Ci）
代码
n = int(input())
a=[int(input()) for _ in range(n)]
# print(l1)
c=[0 for _ in range(n)]
avg=sum(a)//n
for i in range(n-1,0,-1):
c[i-1] = c[i]+avg-a[i]
# 注意下标范围是从0开始的，题解下标从1开始
c.sort()
res=0
for i in range(n):
res+=abs(c[i]-c[(n-1)//2])
print(res)