传统题 2000ms 256MiB

分糖果

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

分糖果

Description

新春在即,小Z准备分发一些糖果给他的朋友们作为新年礼物。为了防止分给朋友的糖果不平衡,小Z决定事先处理一下分配。

现在总共有 nn 堆糖果(可以只有0颗糖),小Z每次可以执行以下操作的其中一种:

  • 从其中任意一堆糖果中取出一颗糖自己吃掉;
  • 从其中任意非空的一堆糖果中取出一颗糖放入另一堆中;

最终小Z要将 nn 堆糖果处理成每堆糖果的数量均相等,请问他最少需要多少次操作?

Input Format

含有多个测试用例。第一行输入一个整数 T ,代表测试用例的数量。

对于每个测试用例,第一行输入一个整数 nn ,表示要分的糖果堆数;

第二行输入 nn 个整数 a1,a2,,ana_1, a_2, \cdots , a_n ,表示初始堆中糖果数量。

保证对于所有测试用例,n106\sum n \le 10^6

Output Format

对于每个测试用例输出一行包含一个整数,表示最少需要的操作次数。

Input Example#1

4
3
1 1 0
4
2 2 2 2
3
0 1 4
1
1000000000

Output Example#1

2
0
3
0

Data Range

$1 \le n \le 10^5, 0 \le a_i \le 10^9, \sum n \le 10^6$ 。

2024年南京师范大学迎新春赛

未参加
状态
已结束
规则
ACM/ICPC
题目
10
开始于
2024-2-7 8:00
结束于
2024-2-9 12:00
持续时间
52 小时
主持人
参赛人数
117