P6392: 瞌睡虫

---

【题目描述】

【题目描述】
奶牛 Bessie 很兴奋最近重返线下上课了！不幸的是，她的讲师 Farmer John 讲课非常无聊，因此她经常在课堂上打瞌睡。
Farmer John 注意到 Bessie 在课堂上没有专心听讲。他让班上的另一名学生 Elsie 记录 Bessie 在一节课中睡着的次数。总共有 N 个课时（1≤N≤10⁵），Elsie 记录下 Bessie 在第 i 个课时睡着了 ai 次（0≤ai≤10⁶）。Bessie 在所有课时期间睡着的总次数不超过 10⁶。
Elsie 感觉与 Bessie 竞争非常激烈，从而想让 Farmer John 觉得 Bessie 在每节课上总是睡着相同的次数——让问题看起来完全是 Bessie 的错，而与 Farmer John 有时无聊的讲课无关。Elsie 可以修改记录的唯一方式是合并两个相邻的课时。例如，如果 a=[1,2,3,4,5]，那么如果 Elsie 合并第二和第三课时则记录将变为 [1,5,4,5]。
帮助 Elsie 计算她需要对记录进行的最小修改次数，使得她可以令记录中的所有数相等。
【输入格式】（从终端 / 标准输入读入）：
输入的第一行包含 一个整数 T（1≤T≤10）表示需要独立求解的子测试用例数量。
以下是 T 个子测试用例，每个子测试用例包含两行。第一行包含 N，第二行包含 a1,a2,…,aN。
输入保证在每个子测试用例中，a 中所有数之和不超过 10⁶。同时输入保证所有子测试用例的 N 之和不超过 10⁵。
【输出格式】（输出至终端 / 标准输出）：
输出 T 行，对每个子测试用例输出 Elsie 可以令记录中的所有数相等所需进行的最小修改次数。
【输入样例】：
3
6
1 2 3 1 1 1
3
2 2 3
5
0 0 0 0 0
【输出样例】：
3
2
0
【样例说明】
对于第一个子测试用例，Elsie 可以通过 3 次修改将使得她的记录中仅包含 3。
   1 2 3 1 1 1
-> 3 3 1 1 1
-> 3 3 2 1
-> 3 3 3
对于第二个子测试用例，Elsie 可以通过 2 次修改将她的记录变为 7。
   2 2 3
-> 2 5
-> 7
对于最后一个子测试用例，Elsie 无需执行任何操作；记录已经由相等的数组成。
 

【输入】

输入的第一行包含 T，为需要求解的子测试用例的数量。以下是 T 个子测试用例，每个子测试用例包含两行。第一行包含 N，第二行包含 a1,a2,…,aN。

输入保证在每个子测试用例中，a 中所有数之和不超过 10⁶。同时输入保证所有子测试用例的 N 之和不超过 10⁵。

【输出】

输出 T 行，对每个子测试用例输出 Elsie 可以令记录中的所有数相等所需进行的最小修改次数。

【提示】

对于第一个子测试用例，Elsie 可以通过 3 次修改将使得她的记录中仅包含 3。

   1 2 3 1 1 1

-> 3 3 1 1 1

-> 3 3 2 1

-> 3 3 3

对于第二个子测试用例，Elsie 可以通过 2 次修改将她的记录变为 7。

   2 2 3

-> 2 5

-> 7

对于最后一个子测试用例，Elsie 无需执行任何操作；记录已经由相等的数组成。

题目类型~

USACO2022-铜牌-2 

咻咻~

提交答案 状态 返回