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

· · 题解

题意

有 n 种牌，每种牌 a_i 个， 有单牌、对子、炸弹和三带一四种出牌方式，问最少出多少次牌才能赢得胜利？

思路

不难发现，出四个牌的方式（即炸弹和三带一）的方式肯定是较优的，那这两种方式那个更优呢？

三带一： 3+1 ；

炸弹： 4 ；

en~~，en！？炸弹可以看成三个同样的牌带一个一样的牌！

so 那就来看新三带一（三个同样的牌带其他任意一种牌）吧：

对于每一种牌，我们可以去统计可以组成三张牌的数量，剩余的牌按两张和一张再存起来（方便书写，我们定义一张牌为 sum1 ，依次类推得sum2,sum3）；

然后我们便可以去把 sum3 和 sum1+2*sum2（单独一张牌的数量）配对了；

此时，我们又遇到问题了，如果 sum3<=sum1+2*sum2 还好，直接去判断就好了，那如果 sum3>sum1+2*sum2 呢 ？

我们可以把 sum3 拆成 sum1 与 sum2 来去和余下的 sum3 配对，再一想，这样的话，那所有的牌不都能参与 4 的构建了吗，然后余下的牌数不就只有 1,2,3 三种可能了吗；

这样这道题就完成了。

AC 代码

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<set>
#include<ctime>
#include<stack>
#define N 300005
#define int long long
using namespace std;
int t;
int a[N];
int re()
{
    int x=0,p=1;
    char y=getchar();
    for(;y>'9'||y<'0';y=getchar())
        if(y=='-')
            p=-p;
    for(;y>='0'&&y<='9';y=getchar())
        x=x*10+y-'0';
    return x*p;
}
void wr(int x)
{
    if(x<0)
        x=-x,putchar('-');
    if(x>9)
        wr(x/10);
    putchar(x%10+'0');
}
signed main()
{
    t=re();
    while(t--)
    {
        int n=re();
        int sum1,sum2,sum3,sum;
        sum1=sum2=sum3=sum=0;
        for(int i=1;i<=n;i++)
            a[i]=re();
        for(int i=1;i<=n;i++)
        {
            sum+=a[i];
            if(a[i]==0)
                continue;
            else if(a[i]==1)
                sum1++;
            else if(a[i]==2)
                sum2++;
            else 
            {
                sum3+=a[i]/3;
                sum2+=(a[i]%3)/2;
                sum1+=(a[i]%3)%2;
            }
        }
        if(sum3<=sum1+2*sum2)
        {
            if(sum3<=sum1)
                wr(sum1+sum2),putchar('\n');
            else 
            {
                int ls=sum2;
                sum2=(2*ls-(sum3-sum1))/2;
                sum1=(2*ls-(sum3-sum1))%2;
                wr(sum3+sum2+sum1),putchar('\n');
            }
        }
        else
        {
            wr(sum/4+sum%4/2+sum%4%2),putchar('\n');
        }
    }
    return 0;
}