---

MT2001幸运的3

原创 已于 2023-07-29 15:44:43 修改 · 粉丝可见 · 437 阅读 · 0 · 2 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/131995280

题目：

你有n个数，可以将它们两两匹配(即将两数首尾相连)，每个数只能使用一次，问匹配后最多有多少个3的倍数（没有进行匹配的数不算）？

样例1：

输入：

<br/>3<br/>123 123 99<br/>

输出：

<br/>1<br/>

思路：

根据 倍数 3 的一个特性   ，某个数值  各个位数相加 是 3 的倍数，那么该数值也是 3 的倍数

所以，根据题意，两数的首尾相连，实际上就是两个数的位数之和，是否是 3 的倍数

其中还有一个特性就是  余数是 1 和余数是 2 的数值相连，就是3的倍数了，因为 1 + 2 == 3

所以AC代码如下：

#include <iostream>
#define endl '\n'
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;

int ans,n, rem[3];	// 全局定义，默认初始值为 0

signed main()
{
	___G;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		int num;
		cin >> num;
		rem[num % 3]++;		// 开始记录数值配对
	}

	// 能被 3 整除的两个数 一定可以凑成被 3 整除的数值

	ans += rem[0] / 2;

	// 余数 为 1 和 余数为 2 的两个数值 一定可以 凑成一个被 3 整除的数值
	// 因为 1 + 2 == 3

	ans += min(rem[1], rem[2]);		// 取最多能配对的数值

	cout << ans << endl;

	return 0;
}