1371 - 均分纸牌

题目描述

n 堆纸牌(2≤n≤200),排成一行,编号分别为 1,2,\dots,n

已知每堆纸牌有一定的张数,且张数之和均为 n 的倍数。移动各堆中的任意张纸牌,使每堆的数量达到相同,且移动次数最少。

移动规则:

每次可以移动任意的张数,第 1 堆可以移向第 2 堆,第 2 堆可以移向第 1 堆或第 3 堆,\dots, 第 n 堆只可以移向第 n-1 堆。

例如,当 n=4 时:

堆号      1     2     3     4 
张数      3     5     4     8

移动的方法有许多种, 其中的一种方案:

① 第 2 堆向第 1 堆移动 2 张,成为:5 3 4 8

② 第 4 堆向第 3 堆移动 3 张,成为:5 3 7 5

③ 第 3 堆向第 2 堆移动 2 张,成为:5 5 5 5

经过三次移动,每堆都成为 5 张。

输入

第一行一个整数 n

第二行 n 个整数,用空格分隔。

输出

一个整数(表示最少移动次数)。

样例

输入

4 
3 5 4 8

输出

3
来源

贪心

标签
题目参数
时间限制 1 秒
内存限制 16 MB
提交次数 1595
通过人数 922
金币数量 2 枚
难度 基础


上一题 下一题