题目
B. Balanced Remainders
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
您将获得一个号码nn (可被整除33） 和数组a[1…n]a[1…n].只需移动一下，即加可将任何数组元素增加一个。正式地，您选择索引ii (1≤i≤n1≤i≤n） 和replace aiai跟ai+1ai+1.您可以选择相同的索引ii多次进行不同的移动。
让我们用c0c0、c1c1和c2c2表示数组aa中的数字数量，当分别除以数字33时，这些数字的余数为00、11和22。假设数组aa具有平衡余数，如果c0c0、c1c1和c2c2相等。
例如，如果n=6n=6和a=[0,2,5,5,4,8]a=[0,2,5,5,4,8]，则以下移动顺序是可能的：
- 最初c0=1c0=1,c1=1c1=1和c2=4c2=4，则这些值彼此不相等。让我们增加a3a3，现在是数组a=[0,2,6,5,4,8]a=[0,2,6,5,4,8];
- c0=2c0=2,c1=1c1=1和c2=3c2=3，则这些值不相等。让我们增加a6a6，现在是数组a=[0,2,6,5,4,9]a=[0,2,6,5,4,9];
- c0=3c0=3,c1=1c1=1和c2=2c2=2，则这些值不相等。让我们增加a1a1，现在是数组a=[1,2,6,5,4,9]a=[1,2,6,5,4,9];
- c0=2c0=2,c1=2c1=2和c2=2c2=2，这些值彼此相等，这意味着数组aa具有平衡的余数。
找到制作阵列所需的最小移动次数aa具有平衡的余数。
Input
第一行包含一个整数tt (1≤t≤1041≤t≤104).然后tt测试用例如下。
每个测试用例的第一行包含一个整数nn (3≤n≤3?1043≤n≤3?104） — 数组的长度aa.保证数量nn可被整除33.
下一行包含nn整数a1,a2,…,ana1,a2,…,an (0≤ai≤1000≤ai≤100).
可以保证nn在所有测试用例中不超过150000150000.
Output
对于每个测试用例，输出一个整数 — 必须为aa数组，使其具有平衡的余数。
题目大意
要求数组元素模3之后余数为0，1，2的个数相同，若不同则可以对每个元素进行加1的操作，求使数组变成目标数组的最小操作次数，如[0,2,5,5,4,8]，模3后余数为[0,2,2,2,1,2]，则c0=1, c1=1 and c2=4 ，找到制作阵列所需的最小移动次数aa具有平衡的余数。
Example
input
Copy
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
output
Copy
3 1 3 0
Note
第一个测试用例在语句中进行了解释
在第二个测试用例中，您需要对i=2i=2.
第三个测试用例需要执行三个步骤：
- 第一步：i=9i=9;
- 第二步：i=9i=9;
- 第三步：i=2i=2.
在第四个测试用例中，值c0c0,c1c1和c2c2最初彼此相等，因此数组aa已经有平衡的余数。
代码
/*思路：
先将每种余数求出，在多的余数中随机选取一位加一，
让它分布到数量少的余数情况中，直到三种余数数量
相同*/
#include <iostream>using namespace std;int main()
{int t;cin >> t;while(t--){int n,c0=0,c1=0,c2=0,s=0,i,m;cin >> n;for(i=0;i<n;i++){cin >>m;if(m%3==0)c0++;else if(m%3==1)c1++;else if(m%3==2)c2++;}while(c1!=c2||c1!=c0||c0!=c2){if(c0>=c1&&c0>=c2)c0--,c1++;/*当c0上余数为0的数加一时，余数为0的少一，余数为一的加一*/else if(c1>=c0&&c1>=c2)c1--,c2++;elsec2--,c0++;s++;}cout << s << endl;}return 0;
}