#K. 「一本通 1.1 练习 6」糖果传递

Type: Default

1000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

原题来自：HAOI 2008

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

第一行有一个整数 $n$ ，表示小朋友个数；

在接下来 $n$ 行中，每行一个整数 $a_i$ 。

输出使所有人获得均等糖果的最小代价。

对于 $30\%$ 的数据， $n \leq 1000$ ；

对于 $100\%$ 的数据， $n \leq 10^6$ ，保证答案可以用 $64$ 位有符号整数存储。