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

· · 题解

「SMOI-R2」Happy Card

上午的模拟赛第一题成功写挂了。本来分类讨论了一百多行喜提 0 分，借助 dalao 的思路重构一下代码。

思路

相较于官方题解，感觉还是有不一样的地方。此题核心的思想就是贪心。对于所有的单张，必然要花费一次打出去，所以最好的情况是三带一打出去。

那么我们先提出所有的三张，跟剩下的数量的牌从小到大分开组合。对于所有都是三张，就要拆开有三张的牌进行组合。实际上我们把炸弹和三带一看成一种东西。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10;
long long a[MAXN];
int main()
{
    int T,n;
    long long sum = 0;
    long long cnt1 = 0 , cnt2 = 0 , cnt3 = 0;
    cin >> T; // 输入询问次数
    for (int t = 1 ; t <= T ; ++t)
    {
        memset(a,0,sizeof(a));
        cnt1 = cnt2 = cnt3 = sum = 0;
        cin >> n;
        for (int i = 1 ; i <= n ; ++i)
        {
            cin >> a[i]; // 输入每种牌的数量
            sum += a[i];
            cnt3 += a[i]/3;// 累加可以组成三张的组合
        }
        if (cnt3 > sum/4) // 如果所有“三张”的总数足以覆盖至少四张一组的分布
        {
            if (sum % 4 == 1) cout << sum / 4 + 1 << endl;
            else if (sum % 4 ==2) cout << sum / 4 + 1 << endl;
            else if (sum % 4 == 3) cout << sum / 4 + 2 << endl;
            else if (sum % 4 == 0) cout << sum / 4 << endl;
        }
        else if (cnt3 <= sum/4)
        {
            for (int i = 1 ; i <= n ; i++)
            {
                if (a[i] % 3 == 1) cnt1++;// 模 3 余 1 的牌数量
                else if (a[i] % 3 == 2) cnt2++;// 模 3 余 2 的牌数量
            }
            if (cnt3 <= cnt1) cout << cnt1 + cnt2 << endl;// 如果“三张”不足够，使用余数牌
            else if (cnt3 > cnt1) cout << cnt3 + cnt2 - (cnt3 - cnt1) / 2 << endl;// 用余数的 2 补充“三带一”或其他牌
        }
    }

    return 0;
}