上课睡觉

题目描述:

有 N 堆石子，每堆的石子数量分别为 a1,a2,…,aN。

你可以对石子堆进行合并操作，将两个相邻的石子堆合并为一个石子堆，例如，如果 a=[1,2,3,4,5]，合并第 2,3 堆石子，则石子堆集合变为 a=[1,5,4,5]。

我们希望通过尽可能少的操作，使得石子堆集合中的每堆石子的数量都相同。

请你输出所需的最少操作次数。

本题一定有解，因为可以将所有石子堆合并为一堆。

输入格式:

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 N。

第二行包含 N 个整数 a1,a2,…,aN。

输出格式:

每组数据输出一行结果。

数据范围:

1 ≤ T ≤ 10 ,
1 ≤ N ≤ 10⁵,
0 ≤ ai ≤ 10⁶,
∑ ai ≤ 10⁶,
每个输入所有 N 之和不超过 105。

样例输入:

3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0

样例输出:

3
2
0

提示:

样例解释

第一组数据，只需要用 33 个操作来完成：

1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3

第二组数据，只需要用 22 个操作来完成：

 2 2 3
-> 2 5
-> 7

第三组数据，我们什么都不需要做。

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2022 February Contest Bronze