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

sansesantongshun · 2024-11-24 13:50:40 · 题解

本题乍一看好像没什么思路，考虑将牌型进行转化。

我们发现炸可以看做三张同种的牌和一张同种的牌，即可以将三带一和炸合并为一种情况，即三带一是三张同种的牌加上任意一张牌。

设有 x 个单牌，y 个对子，z 个三张，那么最终答案为 x+y，同时需满足 z \le x。

初始把所有牌设为单张，如果把三张同种牌合并为三张，答案将减少 3，如果把两张同种牌合并为对子，答案将减少 1。根据贪心策略，应尽可能在允许的情况下尽量将单牌合并为三张，然后在允许的情况下将单牌合并为对子。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int t,n;
long long a[300005],sum,san,er,x;
int main()
{
    cin>>t;
    while (t--)
    {
        scanf("%d",&n);
        sum=0;
        for (int i=1;i<=n;++i)
        {
            scanf("%lld",&a[i]);
            sum+=a[i];//看做单牌
        }
        san=0;
        for (int i=1;i<=n;++i)
        if (a[i]>=3)
        {
            x=min(a[i]/3,sum-san>>2);
            a[i]-=3*x;
            sum-=3*x;
            san+=x;
        }//合并三张
        er=sum-san>>1;
        for (int i=1;i<=n;++i)
        if (a[i]>=2)
        {
            x=min(a[i]>>1,er);
            sum-=x;
            er-=x;
        }//合并对子
        cout<<sum<<'\n';
    }
}