Sleeping in Class

题目描述

奶牛 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

标签: USACO|2022|Bronze

来源

USACO|2022|Bronze