自动搬运

查看原文

来自洛谷，原作者为

	larsr loser

搬运于2025-08-24 23:06:25，当前版本为作者最后更新于2024-11-08 15:48:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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