Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

bzoj 3293: [Cqoi2011]分金币&&1045: [HAOI2008] 糖果传递&&1465: 糖果传递

题目链接

传送门
三道题一模一样 我只给了一个题目

Description

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

Input

第一行一个正整数n,表示小朋友的个数. n行,每行一个整数ai,表示第i个小朋友得到的糖果的颗数.

Output

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

Sample Input

4

1

2

5

4

Sample Output

4

HINT

数据范围
30%的测试数据, n<=1000.
100%的测试数据, n<=1000000.
ai>=0, 保证ai在longint/int范围内, ai的总和在int64/long long范围内.

想说的话

最近某位圆圆的神犇爱上了中位数问题(真是迷)
于是乎我就得到了一系列的中位数习题列表

题解

这道题不过一句话题意就是说我们有一堆糖 每个孩子手里面有点
然后我们希望每个孩子拿到平均数个糖
当然第一步是求出所有糖的平均数
然后我们再开一个数组 记录一下当前这个位置需要变动的糖果数量(假设全都是从后一个人给到前一个人)
接下来对这个数组排序 当然每个位置变到中位数的时候总的代价是最小的

代码

Add a Comment

电子邮件地址不会被公开。 必填项已用*标注

隐藏