专栏文章

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

GGlass_S
P11323题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mir0fm0a
此快照首次捕获于
2025/12/04 13:43
3 个月前
此快照最后确认于
2025/12/04 13:43
3 个月前
查看原文

题意

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

思路

不难发现，出四个牌的方式（即炸弹和三带一）的方式肯定是较优的，那这两种方式那个更优呢？
三带一： 3+13+1 ；
炸弹： 44 ；
en~~，en！？炸弹可以看成三个同样的牌带一个一样的牌！
so 那就来看新三带一（三个同样的牌带其他任意一种牌）吧：
对于每一种牌，我们可以去统计可以组成三张牌的数量，剩余的牌按两张和一张再存起来（方便书写，我们定义一张牌为 sum1 ，依次类推得sum2,sum3）；
然后我们便可以去把 sum3 和 sum1+2*sum2（单独一张牌的数量）配对了；
此时，我们又遇到问题了，如果 sum3<=sum1+2*sum2 还好，直接去判断就好了，那如果 sum3>sum1+2*sum2 呢 ？
我们可以把 sum3 拆成 sum1 与 sum2 来去和余下的 sum3 配对，再一想，这样的话，那所有的牌不都能参与 44 的构建了吗，然后余下的牌数不就只有 1,2,31,2,3 三种可能了吗；
这样这道题就完成了。

AC 代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...