本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-11-25 14:05:23

题意

给你 $n$ 种类型的纸牌，每种有 $v_i$ 张，你可以出 $4$ 中牌型：单张、对子、炸和三带一。问你最少出多少次可以全出完。

$T$ 组数据，$T \le 10$，$n \le 3 \times 10^5$，$0 \le v_i \le 10^9$。

思路

首先，我们可以把炸拆成三张一样的和另一张一样的，也就是拆成三带一。那么我们就可以先把每个 $v_i$ 拆成若干组一样的和 $1$ 张或 $2$ 张。处理完之后，对于一张或两张，肯定是先与三张的组成三带一节省的步数最多。

如果剩下了 $1$ 张或 $2$ 两张一组的，就当成单张或对子打出去。

如果剩下了三张一组的，那么任意四组可以组成 $3$ 次三带一，花 $3$ 步；任意三组可以组成 $2$ 组三带一和 $1$ 个单张，花 $3$ 步；任意两组可以组成 $1$ 个三带一和 $1$ 个对子，花 $2$ 步；剩下一个可以拆成 $1$ 张单张和对子，花 $2$ 步。

按照如上的顺序来一步一步进行，举例可以证明步数最少。

不懂可结合代码食用。

Code

#include <bits\/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n;
int mp[5];
int ans;
int t;
signed main()
{
\/\/	freopen("card.in","r",stdin);
\/\/    freopen("card.out","w",stdout);
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
	cin>>t;
	while(t--)
	{
	    ans=0;
	    for(int i=0;i<=4;i++) mp[i]=0;
	    cin>>n;
	    int f1=0,f2=0;
    	for(int i=1;i<=n;i++)
    	{
    	    int a;
    	    cin>>a;
    	    mp[3]+=a\/3;
    	    a%=3;
    	    mp[a]++;
    	    if(a==1) f1++;
    	    if(a==2) f2++;
        }
        int p=min(mp[1],mp[3]);
        ans+=p;
        mp[3]-=p;
        mp[1]-=p;
        p=min(mp[2]*2,mp[3]);
        ans+=p;
        mp[3]-=p;
        mp[2]-=(p+1)\/2;
        mp[1]+=p%2;
        ans+=mp[3]\/4*3;
        mp[3]%=4;
        if(mp[3]==3) ans+=3;
        else if(mp[3]) ans+=2;
        ans+=mp[1]+mp[2];
        cout<<ans<<endl;
    }
    return 0;
}