题解：P11323 【MX-S7-T1】「SMOI-R2」Happy Card

Ratio_Y · 2024-11-24 18:54:32 · 题解

思路

比较好想到炸弹等价于三带一，因此本质只有三种出牌类型。并且三带一一次能出掉四张牌，显然优先打三带一是很优的。所以我们处理出三带的个数以及剩下零牌中对子的个数，然后分讨。

• 如果三带的个数少于零牌数，此时策略比较好想：三带全部打出，多余的零牌中尽量打对子。

• 如果二者数量相等，那么一直打三带一就结束了。

• 如果三带的个数多于零牌数，我们就要考虑将零牌带完后如何将三带拆开打出。容易发现四个三带可以通过拆掉一个来在三轮内打出，这样依然是最优的一次出四张牌的出法，因此优先选。那么之后只可能剩 0,1,2,3 个三带，简单分讨即可。

那么就做完了，整体思路不难，解题瓶颈在于将炸弹拆成三带一的形式。时间复杂度 \mathcal{O(n)}。

实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int Ratio = 0;

namespace Wisadel
{
    short main()
    {
        int T, n, x; scanf("%d", &T);
        while(T--)
        {
            scanf("%d", &n);
            ll sum3 = 0, sum2 = 0, sum1 = 0, ans = 0;
            for(int i = 1; i <= n; i++)
            {
                scanf("%d", &x);
                sum3 += x / 3;
                sum1 += x % 3;
                if(x % 3 == 2) sum2++;
            }
            if(sum3 < sum1)
            { // 三带不完，全带，剩下考虑对
                ll zc = sum1 - sum3; // 剩下 zc 张
                ll tim = 0; // 出对子数量
                tim = min(sum2, zc / 2);
                zc -= tim * 2;
                ans = sum3 + zc + tim;
            }
            else if(sum3 == sum1) ans = sum3;
            else
            { // 三带多了，拆多的三带
                ll zc = sum3 - sum1;
                ll tim = zc / 4; // 四个三带三次可出完
                if(zc % 4 == 1) ans = 2; // 1 + 2
                else if(zc % 4 == 2) ans = 2; // 3.1 + 2
                else if(zc % 4 == 3) ans = 3; // (3.1) * 2 + 1
                ans += tim * 3 + sum1;
            }
            printf("%lld\n", ans);
        }
        return Ratio;
    }
}
signed main(){return Wisadel::main();}
// All talk and never answer

完结撒花~