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

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

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

设有

x

个单牌，

y

个对子，

z

个三张，那么最终答案为

x+y

，同时需满足

z \le x

。

初始把所有牌设为单张，如果把三张同种牌合并为三张，答案将减少

3

，如果把两张同种牌合并为对子，答案将减少

1

。根据贪心策略，应尽可能在允许的情况下尽量将单牌合并为三张，然后在允许的情况下将单牌合并为对子。

代码如下：

CPP

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

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

文章操作

相关推荐

评论

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