P2192 HXY玩卡片 题解

题目简述

给定一些 $5$ 和 $0$ 的数字，让你在其中选择一些数进行排列成为一个非负整数，使得这个数字能被 $90$ 整除，且是所有满足条件的数中最大的一个，无解输出 $-1$。

题目分析

如果一个数能被 $90$ 整除，那么它一定能被 $9$ 和 $10$ 整除。

• 能被 $10$ 整除，那就说面答案的个位数一定是 $0$，如果没有 $0$ 的话就是无解。
• 能被 $9$ 整除，那就说明答案的各个位加起来的和能被 $9$ 整除，由于答案仅有 $0$ 和 $5$ 组成，所以只需要判断所有 $5$ 加起来能否被 $9$ 整除即可。也就是说，如果有 $x$ 个 $5$，那么需要保证 $5 \cdot x$ 是 $9$ 的倍数，所以有 $x \mid 9$。

有了上面的推导，我们便有了解法：

设一共有 $x$ 个 $5$，因为要满足 $x \mid 9$，所以我们最多只能选 $\lfloor \frac{x}{9} \rfloor \times 9$ 个 $5$。因为要求最大，所以把这些 $5$ 先输出，最后输出有的所有 $0$。但是有可能没有足够的 $5$，这样就只能输出 $0$ 了，当然是在有 $0$ 的情况下。

代码

#include<iostream>
using namespace std;
int n,cnt1,cnt2;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
	    if(ch=='-')
		{
			f=-1;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
	    x=(x<<1)+(x<<3)+ch-48;
	    ch=getchar();
	}
	return x*f;
}
inline void write(int x)
{
    if(x<0)
	{
    	putchar('-');
		x=-x;
	}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int main()
{
	n=read();
	for(int i=0,a=0;i<n;i++)
	{
		a=read();
		a==5?cnt1++:cnt2++;
	} 
	if(cnt1>=9&&cnt2>0)
	{
		for(int i=1;i<=cnt1/9*9;i++)
		{
			printf("5");
		}
		for(int i=1;i<=cnt2;i++)
		{
			printf("0");
		}
	}
	else if(cnt2>0)
	{
		printf("0");
	}
	else printf("-1");
	return 0;
}