【MX-S7-T1】「SMOI-R2」Happy Card 题解
刘梓轩2010
·
·
题解
题意
给你 n 种类型的纸牌，每种有 v_i 张，你可以出 4 中牌型：单张、对子、炸和三带一。问你最少出多少次可以全出完。
## 思路
首先，我们可以把炸拆成三张一样的和另一张一样的，也就是拆成三带一。那么我们就可以先把每个 $v_i$ 拆成若干组一样的和 $1$ 张或 $2$ 张。处理完之后，对于一张或两张，肯定是先与三张的组成三带一节省的步数最多。
如果剩下了 $1$ 张或 $2$ 两张一组的，就当成单张或对子打出去。
如果剩下了三张一组的，那么任意四组可以组成 $3$ 次三带一，花 $3$ 步；任意三组可以组成 $2$ 组三带一和 $1$ 个单张，花 $3$ 步；任意两组可以组成 $1$ 个三带一和 $1$ 个对子，花 $2$ 步；剩下一个可以拆成 $1$ 张单张和对子，花 $2$ 步。
按照如上的顺序来一步一步进行，举例可以证明步数最少。
不懂可结合代码食用。
## Code
```c++
#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;
}
```