题解：P11323 【MX-S7-T1】「SMOI-R2」Happy Card
Tenil
·
·
题解
Solution
闲话
蒟蒻第一次写题解，若有不当还请海涵。
题意
## 分析
逐类考虑：
首先，某类牌多于4张时无脑炸不是最优（本蒟蒻在这里先死了10分钟），只要看一眼样例的例一不难得出——
>[1,1,1,1][1][2]：3步
>
>
>[1,1,1,2][1,1]：2步
因此考虑拆掉：2+2完全亏，因此全部拆为1+3.
可以发现，三带一的方式是比较特殊的。容易想到：如果有能匹配的不匹配，则会造成2步浪费。故一定要优先匹配。但仅单牌和三个匹配可能有三个的数量多的情况，再考虑对子；
由拆炸为三带一自然想到对子可以拆成两个单牌：有三张相同和一个对子剩余时，拆2步，不拆3步，所以必拆补齐。（当然，无脑拆显然亏）
最后要是还有三个相同的剩余，考虑互相补足：只有$1\times3$直接出（2步），$2\times3$拆成三带一加一对（2步），$3\times3$为两个三带一加一张单牌，（3步）$4\times3$则为三个三带一（3步）。$4\times3$直接拆完，因此多于$4\times3$的情况$(4n+r)\times3$步数为$3n$加上$r\times3$的步数。
于是此题得解。
## 实现
读入每类牌张数，直接全拆成3张的。
按$cnt_1$+$cnt_2\times2$、$cnt_1$与$cnt_3$的大小写$if$条件即可。
详情请见代码——
## Code
```cpp
#include <iostream>
#include <cstdio>
#include <cctype>
using namespace std;
typedef long long ll;//开long long好习惯
inline ll fr() {
ll x=0; char c=getchar();
while(!isdigit(c)) c=getchar();//听说用isdigit()比char比大小快
while(isdigit(c)) {
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
return x;
}
const int maxn=1e6;
ll T,n,v,ans;
//T-数据组数 n-牌种数 v-当前牌种张数 ans-answer
int main() {
T=fr();
while(T--) {
n=fr();
ans=0;
ll cnt[4]={0,0,0,0};//张数为下标的牌堆组数
//多测不清空，直接见祖宗
for(register int i = 0; i < n; i++) {
v=fr();
cnt[3]+=v/3;
cnt[v%3]++;//直接分3
}
ll s=cnt[1]+2*cnt[2];//能分出1的数量
if(s>=cnt[3]) {//1多
if(cnt[1]>=cnt[3]) ans=cnt[1]+cnt[2];//单牌就够，对子直接出
else {
ans+=cnt[1];
cnt[3]-=cnt[1];//先用单牌填
ans+=cnt[3];
cnt[2]-=cnt[3]/2;//再用对子
ans+=cnt[2];//对子直接出
}
}
else {//3多
cnt[3]-=s;//能匹配的先匹配
ans=s+cnt[3]/4*3;//4x3的先考虑
cnt[3]%=4;
if(cnt[3]%3) ans+=2;//r=1,2时%3都非0
else if(cnt[3]) ans+=3;//为0时可能就是0
}
printf("%lld\n",ans);
//华丽输出
}
return 0;
}
```
## 后话
请切记：一拍脑子出的结论一定要验算一下（如本蒟蒻先丢完炸弹的愚蠢想法），不然拿着错结论代码写出花来都过不了。
如果有用还请点个赞！
审核求过啊！