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

· · 题解

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

本题思维难度较大，难度应为黄题~绿题。

思路

这题乍一看需要朴素的模拟，但这样毫无头绪，因为时间复杂度极劣（相当于搜索，为组合数级别 ）。

于是我们来分析题目中的定义：

通过观察可以发现， 3 张类型相同的牌与任意类型的 1 张牌（包括与它类型相同的牌）组合，无论是“炸”还是“三带一”均可一起打出。即：3 张相同的牌与单牌组合可以最大程度上增加一次打出的牌的数量。

我们不妨把所有牌按每相同三张牌一组来划分，统计每组牌的数量，同时记录划分后剩下的“单牌”和“对子”的数量。借助上述贪心思想，我们想到用三张牌的牌组组合“单牌”打出，因为一次打出四张牌必然是最优的出牌方案。 如果牌组数过多，可以考虑将“对子”拆为“单牌”，再与牌组组合。

但注意到我们最多需要总牌数的 1/4 的牌组数来消耗“单牌”（即将牌全部等分为牌组和“单牌”）,如果实际的牌组数大于我们需要的数量，那么我们完全可以将剩余的牌组以 4 张一组组合，多出来的一定为同类牌，可能是 1 张”单牌“， 1 张“对子”，或 1 张”单牌“和 1 张“对子”，打出即可。

综上，牌组数小于等于总牌数的 1/4 时，将牌组与“单牌”尽可能组合，必要时将“对子”拆为“单牌”。

若牌组数大于总牌数的 1/4 时，将牌每四张一组打出，最后剩下的相同的牌特判即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
long long thrd,sgl,dbl;
long long sum;
int vol[MAXN];
int n;
vector<long long> res;
void init()
{
    memset(vol,0,sizeof(vol));
    sum=thrd=sgl=dbl=0;//记得清零
}
int main()
{
    //freopen("card4.in","r",stdin);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        init();
        for(int i=1;i<=n;i++)
        {
            cin>>vol[i];
            sum+=vol[i];
            if(vol[i]%3 == 1) sgl++;
            if(vol[i]%3 == 2) dbl++;
            thrd+=vol[i]/3;//统计最优的出牌方法
        }
        long long ans=0;
        if(thrd > sum/4)//均可四张一组打出
        {
            if(sum%4 == 1 || sum%4 == 2) ans=sum/4+1;
            if(sum%4 == 3) ans=sum/4+2;
            if(sum%4 == 0) ans=sum/4;
        }
        else
        {
            if(thrd < sgl) ans=sgl+dbl;//牌组数小于单牌数
            else if(sgl <= thrd && thrd <= sgl+dbl*2) ans=thrd+(dbl*2+sgl-thrd)/2+(dbl*2+sgl-thrd)%2;//拆对子
        }
        res.push_back(ans);
    }
    for(auto p:res)
    {
        cout<<p<<endl;
    }
    return 0;
}