算法刷题【洛谷U193902】橡皮泥
2022-04-18
题目描述
陶陶有 n 个橡皮泥，每个橡皮泥的体积为 ai 。
陶陶是一个泥人巨匠，于是他可以进行以下操作：
每次操作选择两个橡皮泥，将其合并，新橡皮泥的体积为两个原体积之和，并将合成后的橡皮泥插入原序列，当然插入的位置无关紧要。
例如，三个橡皮泥的体积为 [2, 1, 4] ，陶陶能够获得 [3, 4], [1, 6] 或 [2, 5] 。
陶陶想知道经过若干次操作后，体积是 3 的倍数的橡皮泥个数最多是多少个？
输入格式
第一行一个整数 T 。
接下来 T 组数据，每组数据第一行为一个整数 n ，接下来一行有 n 个整数，表示这 n 个橡皮泥的体积。
输出格式
对于每组数据，输出体积是 3 的倍数的橡皮泥个数最多是多少个
输入输出样例
In 1：
2
5
3 1 2 3 1
7
1 1 1 1 1 2 2Out 1：
3
3数据范围
对于100%的数据点：1≤T≤1000,1≤n≤100,1≤ai≤109
题解
显而易见：
- 本身是三的倍数直接统计；
- 不是的优先一个
除以3余数为1的数和一个除以3余数为2的数配对（因为这样消耗的数字少，严格证明我也不会）； - 再针对多余出来的数字（这些数字取余3的余数一定单调为1或者2），每3个相加配成一个3的倍数。
#include <bits/stdc++.h>
using namespace std;
int n, temp, ans = 0;
int main() {
int tttt;
cin >> tttt;
while (tttt--) {
cin >> n;
ans = 0; // 总共可以形成多少
int one = 0, two = 0; // 余数为1或2的数字的个数
for (int i = 1; i <= n; i++) {
cin >> temp;
if (temp % 3) {
// 不是3的倍数，记录余数是几的个数
temp % 3 == 1 ? one++ : two++;
} else
ans++; // 是3的倍数则直接累加
}
ans += min(one, two); // 一个余数为1的数字和一个余数为2的数字可以凑成一个3的倍数
ans += abs(one - two) / 3; // 多余的部分，每3个数可以凑成一个3的倍数，向下取整
cout << ans << endl;
}
}