#P1465. 糖果传递

    ID: 477 传统题 1000ms 512MiB 尝试: 788 已通过: 355 难度: 6 上传者: 标签>CF1900普及+/提高-一维前缀和中位数最小化绝对偏差和快速选择高精度加法

糖果传递

本场部分分与下发大数据

组别 数据限制 本组分值
1 n≤1000n\le1000 30
2 n≤106n\le10^6 70

各组内按测试点等分累计,每点10分;两组独立累加,总分100。与原题30%、100%的分档一致。

下载大样例(输入与答案)


题目描述

老师准备了一堆糖果, 恰好 nn 个小朋友可以分到数目一样多的糖果. 老师要 nn 个小朋友去拿糖果, 然后围着圆桌坐好, 第1个小朋友的左边是第 nn 个小朋友, 其他第 ii 个小朋友左边是第 i−1i-1 个小朋友. 大家坐好后, 老师发现, 有些小朋友抢了很多的糖果, 有的小朋友只得到了一点点糖果, 甚至一颗也没有 , 设第 ii 个小朋友有 aia_i 颗糖果. 小朋友们可以选择将一些糖果给他左边的或者右边的小朋友, 通过”糖果传递”最后使得每个小朋友得到的糖果数是一样多的, 假设一颗糖果从一个小朋友传给另一个小朋友的代价是 11, 问怎样传递使得所耗的总代价最小.

输入格式

第一行一个正整数 nn ,表示小朋友的个数.

nn 行,每行一个整数 aia_i,表示第 ii 个小朋友得到的糖果的颗数.

输出格式

输出只有一个数, 表示最小代价.

4                               
1
2
5
4
4

提示

数据范围 30%的测试数据, n≤1000n\leq 1000.

100%的测试数据, n≤1000000n\leq 1000000,ai≥0a_i\geq 0, 保证 aia_i 在longint/int范围内, aia_i 的总和在int64/long long范围内.