摘要
Title: 122. 糖果传递
Tag: 中位数、贪心
Memory Limit: 64 MB
Time Limit: 1000 ms

122. 糖果传递

题意

有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为 1。
求使所有人获得均等糖果的最小代价。
思路

图解: Link
最后问题会转换为，多个绝对值相加，求最小值的问题
即
$|x_n - c_1|+|x_n - c_2|+|x_n - c_3|+...+|x_n - c_n|$
那么就求 $c_{1-n}$ 的中位数即可

代码

'''
Author: NEFU AB-IN
Date: 2022-03-30 11:24:05
FilePath: \ACM\Acwing\122.py
LastEditTime: 2022-03-30 14:45:58
'''
N = int(1e6 + 10)
n = int(input())
a, s, c = [0], [0] * N, []

for i in range(1, n + 1):
    a.append(int(input()))
    s[i] = s[i - 1] + a[i]

b = sum(a) // n
for i in range(1, n):
    c.append(i * b - s[i])
c.append(0)

c.sort()

ans = 0
for i in range(n):
    ans += abs(c[i] - c[n // 2])
print(ans)

122. 糖果传递

题意

思路

代码