4457: 「一本通 1.1 练习 6」糖果传递
[Creator : ]
Description
有 $n$ 个小朋友坐成一圈,每人有 $a_i$ 个糖果。每人只能给左右两人传递糖果。每人每次传递一个糖果代价为 $1$。
求使所有人获得均等糖果的最小代价。
求使所有人获得均等糖果的最小代价。
Input
第一行一个正整数 $n\ (n≤1,000,000)$,表示小朋友的个数.
接下来 $n$ 行,每行一个整数 $a_i$,表示第 $i$ 个小朋友得到的糖果的颗数.
接下来 $n$ 行,每行一个整数 $a_i$,表示第 $i$ 个小朋友得到的糖果的颗数.
Output
求使所有人获得均等糖果的最小代价。
Constraints
对于 $30\%$ 的数据,$n \leq 10^3$;
对于 $100\%$ 的数据,$n \leq 10^6$,保证答案可以用 $64$ 位有符号整数存储。
对于 $100\%$ 的数据,$n \leq 10^6$,保证答案可以用 $64$ 位有符号整数存储。
Sample 1 Input
4
1
2
5
4
Sample 1 Output
4