版权信息

​来源​: 自定义题目 ​题目名称​: 均分纸牌

---

任务总览表

• ​任务名称​: 均分纸牌
• ​时间限制​: 1秒
• ​内存限制​: 256MB
• ​分数​: 100

---

题目描述

有 n 堆纸牌（2 ≤ n ≤ 200），排成一行，编号分别为 1, 2, …, n。 已知每堆纸牌有一定的张数，且张数之和均为 n 的倍数。移动各堆中的任意张纸牌，使每堆的数量达到相同，且移动次数最少。 移动规则：每次可以移动任意的张数，第 1 堆可以移向第 2 堆，第 2 堆可以移向第 1 堆或第 3 堆，……第 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

---

提示

• 输入数据保证每堆纸牌的张数之和是 n 的倍数。

---

题目分析

目标

• 通过模拟每堆纸牌的移动，计算最少的移动次数使得每堆纸牌的数量相同。

思路

• 计算每堆纸牌的均分数，即总张数除以 n。
• 从左到右遍历每堆纸牌，累积每堆纸牌与均分数的差值，然后把这个差值传递给下一堆纸牌，直到所有堆的纸牌数量相同。
• 需要统计移动次数，移动次数即为纸牌的差值的绝对值之和。

优化

• 使用累积差值的方式减少不必要的重复计算，通过递推的方式确保每次移动最小。

---

时间复杂度分析

• 遍历一次所有堆纸牌，计算每堆与均分数的差值，因此时间复杂度为 ​**O(n)**​。

---

结论

通过累积差值的方式，我们能够高效地计算出最少的移动次数，确保每堆纸牌的数量最终相同。