自动搬运

查看原文

来自洛谷，原作者为

	minstdfx Believe in the beauty of life, maintain an optimistic attitude, and know that ... is always invincible

搬运于2025-08-24 23:13:21，当前版本为作者最后更新于2025-04-12 23:51:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

闲话

这出题人是不是吃拼好饭吃的脑积水了想出来的这题

题解

首先注意到只和每个数的数码 $6$ 的个数有关。

然后注意到所有 $6$ 的个数不小于 $6$ 的数单成一组是不劣的。

接着注意到对 $5$ 拿尽可能小的数去组二元组是不劣的，因为 $5$ 只需要且总要和另一个数组。

接下来是 $1234$ 的情况，发现因为 $1$ 必然此时要和两个组，那么把 $1$ 打包去和 $4$ 按照 $5$ 的贪心去做也同理不劣（边界条件 $4+1+2$ 不优于 $4+2$）。

接下来对 $123$ 的情况，由于最多要三元组所以不能 $3+1+1+1$，首先 $3+2+1$ 不劣于 $3+2+2$，然后 $3+2+1$ 不劣于 $3+3$（因为 $1$ 没有 $2,3$ 就废了）。

对于只有 $23$ 的情况，有一个上界是 $(3c_3+2c_2)/6$，枚举两个 cnt 的余数发现是紧的。

否则 $1$ 是没有用的。

然后就做完了。

a,b,c,d,e,f,g,d,_,*p;main(C){scanf("%*d");for(;~C;)(C=getchar())<48?(++*(&a+_),_=0):(_+=C==54&&_<6);for(p=&b;f>0;)_=1+(p==&f),(*p<_||(++g,--f,--*p)<_)&&++p;for(p=&b;e>0;)_=1+(p==&b||p==&e),(*p<_||(++g,p<&e&&--e,*p-=_)<_)&&++p;for(;b*d*c;--b,--d,--c)++g;printf("%d",g+(3*d+2*c)/6);}

什么，看不懂吗？

int main()
{
	cin>>n;
	for(int i=1,a;i<=n;++i)
		cin>>a,c[count6(a)]+=1;
	int ans=c[6];
	int ptr=1;
	while(c[5]>0)
	{
		int cc=(ptr==5)+1;
		if(cc>c[ptr] || (++ans,c[5]-=1,c[ptr]-=1)<cc) ++ptr;
	}
	while(c[4]>0 && c[1]>1)
	{
		--c[4]; --c[1]; --c[1];
		++ans;
	}
	ptr=2;
	while(c[4]>0)
	{
		int cc=(ptr==4)+1;
		if(cc>c[ptr] || (++ans,c[4]-=1,c[ptr]-=1)<cc) ++ptr;
	}
	while(c[3] && c[2] && c[1])
	{
		--c[3]; --c[2]; --c[1];
		ans++;
	}
	ans+=(3*c[3]+2*c[2])/6;
}