USACO

USACO 2022 February Contest, Bronze

Problem 1. Sleeping in Class

Contest has ended.

Log in to allow submissions in analysis mode

奶牛 Bessie 很兴奋最近重返线下上课了！不幸的是，她的讲师 Farmer John 讲课非常无聊，因此她经常在课堂上打瞌睡。

Farmer John 注意到 Bessie 在课堂上没有专心听讲。他让班上的另一名学生 Elsie 记录 Bessie 在一节课中睡着的次数。总共有 $N$ 个课时（ $1\le N\le 10^5$ ），Elsie 记录下 Bessie 在第 $i$ 个课时睡着了 $a_i$ 次（ $0\le a_i\le 10^6$ ）。Bessie 在所有课时期间睡着的总次数不超过 $10^6$ 。

Elsie 感觉与 Bessie 竞争非常激烈，从而想让 Farmer John 觉得 Bessie 在每节课上总是睡着相同的次数——让问题看起来完全是 Bessie 的错，而与 Farmer John 有时无聊的讲课无关。Elsie 可以修改记录的唯一方式是合并两个相邻的课时。例如，如果 $a=[1,2,3,4,5]$ ，那么如果 Elsie 合并第二和第三课时则记录将变为 $[1,5,4,5]$ 。

帮助 Elsie 计算她需要对记录进行的最小修改次数，使得她可以令记录中的所有数相等。

输入格式（从终端 / 标准输入读入）：

每个测试用例包含

$T$ （

$1\le T\le 10$ ）个需要独立求解的子测试用例。

输入的第一行包含 $T$ ，为需要求解的子测试用例的数量。以下是 $T$ 个子测试用例，每个子测试用例包含两行。第一行包含 $N$ ，第二行包含 $a_1,a_2,\ldots,a_N$ 。

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

输出格式（输出至终端 / 标准输出）：

输出 $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 无需执行任何操作；记录已经由相等的数组成。

供题：Jesse Choe

Contest has ended. No further submissions allowed.