专栏文章

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

RRatio_Y
P11323题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir0diqv
此快照首次捕获于
2025/12/04 13:41
3 个月前
此快照最后确认于
2025/12/04 13:41
3 个月前
查看原文

思路

比较好想到炸弹等价于三带一，因此本质只有三种出牌类型。并且三带一一次能出掉四张牌，显然优先打三带一是很优的。所以我们处理出三带的个数以及剩下零牌中对子的个数，然后分讨。
  • 如果三带的个数少于零牌数，此时策略比较好想：三带全部打出，多余的零牌中尽量打对子。
  • 如果二者数量相等，那么一直打三带一就结束了。
  • 如果三带的个数多于零牌数，我们就要考虑将零牌带完后如何将三带拆开打出。容易发现四个三带可以通过拆掉一个来在三轮内打出，这样依然是最优的一次出四张牌的出法，因此优先选。那么之后只可能剩 0,1,2,30,1,2,3 个三带，简单分讨即可。
那么就做完了，整体思路不难，解题瓶颈在于将炸弹拆成三带一的形式。时间复杂度 O(n)\mathcal{O(n)}。

实现

CPP
#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
完结撒花~

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...