Happy Card 题解

larsr · 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;
}