CF43C Lucky Tickets 题解

本文主要是介绍CF43C Lucky Tickets 题解，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目大意：

给出 \(N\) 个数，分别为 \(a_1,a_2,...,a_n\) 。将其中任意两个数进行首尾相接组合，每个数只能使用一次，求最大能获得3的倍数的个数。

题解：

此题出现了“3的倍数”，根据数学知识，易得如果一个数的各位数字之和是3的倍数，那么这个数是3的倍数。反过来也成立。

那么，拼成的数是3的倍数有几种情况呢？

假设我们使用 \(x\) , \(y\) 进行拼凑，拼凑成的数为 \(z\) 。

• 如果 \(x\) , \(y\) 都是3的倍数，代表 \(x\) , \(y\) 的各位数字之和都是3的倍数，拼凑后 \(z\) 各位数字之和也是3的倍数，所以 \(z\) 是3的倍数。
• 如果 \(x\) , \(y\) 其中一个数模3余1，另一个数模3余2，代表其中一个数各位数字之和模3余1，另一个数各位数字之和模3余2，拼凑后 \(z\) 各位数字之和为3的倍数（余数1+2=3模3余0），所以 \(z\) 是3的倍数。

当且仅当两数满足上述两个条件之1时，拼凑成的数是3的倍数。

又因为题目中数的大小并不影响最终结果，所以我们首先可以将这些数按模3的余数分成3类，将模3余0，1，2的数的总个数分别存在 \(three\) , \(one\) , \(two\) 中。

那么答案是多少？

因为每个数只能用一次，所以：

• 对上述情况1， \(x\) , \(y\) 都是3的倍数，每两个数能拼凑成一个符合要求的新数，所以情况1的答案为 \(three/2\)（注意此处的除是除完之后向下取整，相当于 Pascal 中的 div ，可以过滤掉剩余最后一个数的情况）。
• 对上述情况2，分别需要一个模3余1与模3余2的数，这样的两个数能拼凑成一个符合要求的新数，当拿不出两个中的任意一个数时，就结束统计，所以答案为 \(min(one,two)\)。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=10000+10;
int n,three,two,one;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
	    int t;
		scanf("%d",&t);
		if(t%3==0) three++;
		if(t%3==1) one++;
		if(t%3==2) two++;
	}
	printf("%d\n",three/2+min(one,two));
	return 0;
}

这篇关于CF43C Lucky Tickets 题解的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！