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

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

思路

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

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

单牌：出一张单牌。
对子：出两张同种的牌。
炸：出四张同种的牌。
三带一：出三张同种的牌和一张不同种的牌。

通过观察可以发现，

3

张类型相同的牌与任意类型的

1

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

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

但注意到我们最多需要总牌数的

1/4

的牌组数来消耗“单牌”（即将牌全部等分为牌组和“单牌”）,如果实际的牌组数大于我们需要的数量，那么我们完全可以将剩余的牌组以

4

张一组组合，多出来的一定为同类牌，可能是

1

张”单牌“，

1

张“对子”，或

1

张”单牌“和

1

张“对子”，打出即可。

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

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

代码

CPP

#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;
}

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

文章操作

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

思路

代码

相关推荐

评论

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