题解 P2192 【HXY玩卡片】

· · 题解

比较坑人但数据较水的一道题

分析

在看题时，要注意以下几点：

  1. 卡片上只有0或者5两个数

  2. HXY可以选择一些卡片

  3. 数字最大且能被90整除

4. 根据样例1，0可以单独输出（这一点很坑人，因为题目中明确说了0不能作为这串数的首位）

重点分析第三点，综合第一点，我们发现：组成的数字各个位数的和能被9整除，并且最后一位必须是0（否则不能被90整除）。

我们用five表示5的个数，zero表示0的个数，我们发现：组成的数字各个位数的和为5×five，为了保证其能被9整除，必须要保证数字中5的个数为9的倍数。

因此可以做一下讨论：

  1. zero == 0 时，必须输出-1。因为这样的数一定不能被10整出，进而不能被90整除

  2. zero ！= 0 and five < 9 时，必须输出0。

  3. zero ！= 0 and five >= 9 时，输出的5的个数为a，a为最大的满足 a <= five，且a为9的整数倍。

最后，为了保证数字最大，很容易得到要让5尽量排在前面。又由于0必须出现在最后一位，没有出现冲突，所以我们很高兴，只需要让所有的5排在所有的0前面即可。

代码


//头文件省略
int N;
int main()
{
    int i;
    int temp;
    int five = 0;
    int zero = 0;
    scanf("%d", &N);
    for(i = 0; i < N; i++)
    {
        scanf("%d", &temp);
        if(temp == 5)
        {
            five++;
        }
        else if(temp == 0)
        {
            zero++;
        }
    }
    //以下判断的分类逻辑不是很清晰，建议先看“分析”部分
    if(five < 9 && zero != 0)
    {
        printf("0");
        return 0;
    }
    if((five < 9 && zero == 0) || zero == 0)
    {
        printf("-1");
    }
    if(five % 9 == 0)
    {
        for(i = 1; i <= five; i++)
        {
            printf("5");
        }
        for(i = 1; i <= zero; i++)
        {
            printf("0");
        }
        return 0;
    }
    else
    {
        //这步实现“分析”中的“输出的5的个数为a，a为最大的满足 a <= five，且a为9的整数倍的数”
        for(temp = five; temp % 9 != 0; temp--);
        for(i = 1; i <= temp; i++)
        {
            printf("5");
        }
        for(i = 1; i <= zero; i++)
        {
            printf("0"); 
        }
        return 0;
    }
}```
对于此题的数据，我只想说太水了。第一提交忘记数字最后一位必须为0，否则不能被10整除，但是却AC了，后来才发现。