对于"三带一"和"王炸"，可以合并成一种出牌方式，即三张同种的牌带上一个牌。可以发现一定是尽可能多出的四张牌。可以先把每三张同种的牌拿出来，那么每种牌只会剩下不超过 2 张牌。

对于剩下的牌，让它们与三张同种的牌配对，会有两种情况。

• 如果没有剩下的牌都配对完了，那么没有被配对的三张同种的牌就自行配对即可，这一定是最优的，因为会达到答案下界 $\lfloor \frac{n}{4} \rfloor + \lfloor \frac{n\mod 4}{2} \rfloor + (n\mod 2)$。
• 否则，优先让只剩下单独一张的牌先匹配，再匹配两张的，还有剩下的就出单牌和对子即可。

那么就可以 $O(n)$ 解决。

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
int t, n;
void slove()
{
	ll sall = 0, s1 = 0, s2 = 0, ds = 0;
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
	{
		ll v;
		scanf("%lld", &v);
		ds += v;
		sall += v / 3;
		if(v % 3 == 1)s1++;
		if(v % 3 == 2)s2++;
	}
	if(s1 + s2 * 2 <= sall)
	{
		printf("%lld\n", ds / 4 + (ds / 2 % 2) + ds % 2);
		return;
	}
	ll la = sall;
	ll tmp = min(s1, sall);
	s1 -= tmp;
	sall -= tmp;
	tmp = min(s2 * 2, sall);
	s2 -= tmp / 2;
	sall -= tmp;
	printf("%lld\n", s1 + s2 + la);
}
int main()
{
	scanf("%d", &t);
	while(t--)slove();
	return 0;
}

by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
typedef long long LL;
LL a[N], r[5];
int main(){
    int T; scanf("%d", &T);
    r[0]=0; r[1]=1; r[2]=1; r[3]=2;
    while(T--){
        int n; scanf("%d", &n);
        LL s1=0, s2=0, s3=0, ans=0;
        for(int i=1; i<=n; i++){
            scanf("%lld", &a[i]);
            s1+=(a[i]%3==1);
            s2+=2*(a[i]%3==2);
            s3+=a[i]/3; 
        }
        if(s1+s2<s3){
            ans+=s1+s2;
            s3-=s1+s2;
            s3*=3;
            ans+=s3/4 + r[s3%4];
        }
        else{
            ans+=s3;
            LL t=s3-s1;
            if(t>0) s2-=t;
            else ans+=-t;
            ans+=s2/2 + r[s2%2];
        }
        printf("%lld\n", ans);
    }
    return 0;
}