← 返回题目列表

Codeforces · 1490/B

B. 平衡余数

中文机器翻译题面 查看原题

给你一个数字$$$n$$$(可被$$$3$$$整除)和一个数组$$$a[1 \dots n]$$$。一步操作中,您可以将任意数组元素加一。形式上,您选择索引 $$$i$$$ ($$$1 \le i \le n$$$) 并将 $$$a_i$$$ 替换为 $$$a_i + 1$$$。您可以为不同的移动多次选择相同的索引 $$$i$$$。

让我们用 $$$c_0$$$、$$$c_1$$$ 和 $$$c_2$$$ 分别表示数组 $$$a$$$ 中除以数字 $$$3$$$ 后余数为 $$$0$$$、$$$1$$$ 和 $$$2$$$ 的数字的数量。假设如果 $$$c_0$$$、$$$c_1$$$ 和 $$$c_2$$$ 相等,则数组 $$$a$$$ 具有平衡余数。

例如,如果 $$$n = 6$$$ 且 $$$a = [0, 2, 5, 5, 4, 8]$$$,则可能有以下移动顺序:

- 最初 $$$c_0 = 1$$$、$$$c_1 = 1$$$ 和 $$$c_2 = 4$$$,这些值彼此不相等。我们增加 $$$a_3$$$,现在数组 $$$a = [0, 2, 6, 5, 4, 8]$$$;
- $$$c_0 = 2$$$、$$$c_1 = 1$$$ 和 $$$c_2 = 3$$$,这些值不相等。让我们增加 $$$a_6$$$,现在数组 $$$a = [0, 2, 6, 5, 4, 9]$$$;
- $$$c_0 = 3$$$、$$$c_1 = 1$$$ 和 $$$c_2 = 2$$$,这些值不相等。我们增加 $$$a_1$$$,现在数组 $$$a = [1, 2, 6, 5, 4, 9]$$$;
- $$$c_0 = 2$$$, $$$c_1 = 2$$$ and $$$c_2 = 2$$$, these values are equal to each other, which means that the array $$$a$$$ has balanced remainders.

求使数组 $$$a$$$ 具有平衡余数所需的最小移动次数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 3 \cdot 10^4$$$) — 数组 $$$a$$$ 的长度。保证数字 $$$n$$$ 能被 $$$3$$$ 整除。

下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 100$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$150\,000$$$。

输出

For each test case, output one integer — the minimum number of moves that must be made for the $$$a$$$ array to make it have balanced remainders.

示例

输入 #1

4
6
0 2 5 5 4 8
6
2 0 2 1 0 0
9
7 1 3 4 2 10 3 9 6
6
0 1 2 3 4 5

输出 #1

3
1
3
0

注意

第一个测试用例在语句中进行了解释。

在第二个测试用例中,您需要为 $$$i=2$$$ 移动一步。

第三个测试用例需要进行三步操作:

- 第一步:$$$i=9$$$;
- 第二步:$$$i=9$$$;
- 第三步:$$$i=2$$$。

In the fourth test case, the values $$$c_0$$$, $$$c_1$$$ and $$$c_2$$$ initially equal to each other, so the array $$$a$$$ already has balanced remainders.