2279. 宝石合并
1000ms
256MB
简单
题目描述
懒🐏🐏有 $N$ 堆宝石，每堆数量为 $a_i$。他希望通过合并**相邻**堆的方式，使得最终剩下的所有堆宝石数量都相等。请问最少需要合并多少次？
**注意**：合并相邻两堆算作 1 次操作。如果最终只剩下一堆，也是一种合法情况。
输入格式
- 第一行包含一个整数 $T$，表示测试数据组数。
- 对于每组数据：
- 第一行是一个整数 $N$ ($1 \le N \le 10^5$)。
- 第二行是 $N$ 个正整数 $a_i$ ($1 \le a_i \le 10^6$)，宝石总数 $\sum a_i \le 10^6$。
输出格式
对于每组测试数据，输出一行一个整数，表示最少合并次数。
样例 1
输入 (Input)
输出 (Output)
样例说明
- **样例解释**：原序列为 `1 2 3 1 1 1`。可以合并前两堆得到 `3 3 1 1 1`，再合并最后三堆得到 `3 3 3`。总共操作了 $(2-1) + (3-1) = 3$ 次。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功