题目大意:
给出 \(N\) 个数,分别为 \(a_1,a_2,...,a_n\) 。将其中任意两个数进行首尾相接组合,每个数只能使用一次,求最大能获得3的倍数的个数。
题解:
此题出现了“3的倍数”,根据数学知识,易得如果一个数的各位数字之和是3的倍数,那么这个数是3的倍数。反过来也成立。
那么,拼成的数是3的倍数有几种情况呢?
假设我们使用 \(x\) , \(y\) 进行拼凑,拼凑成的数为 \(z\) 。
当且仅当两数满足上述两个条件之1时,拼凑成的数是3的倍数。
又因为题目中数的大小并不影响最终结果,所以我们首先可以将这些数按模3的余数分成3类,将模3余0,1,2的数的总个数分别存在 \(three\) , \(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; }