PAT Basic 1023 组个最小数

给定数字 0-9 各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意 0 不能做首位）。例如：给定两个 0，两个 1，三个 5，一个 8，我们得到的最小的数就是 10015558。

现给定数字，请编写程序输出能够组成的最小的数。

输入格式：
输入在一行中给出 10 个非负整数，顺序表示我们拥有数字 0、数字 1、……数字 9 的个数。整数间用一个空格分隔。10 个数字的总个数不超过 50，且至少拥有 1 个非 0 的数字。

输出格式：
在一行中输出能够组成的最小的数。

输入样例：

2 2 0 0 0 3 0 0 1 0

输出样例：

10015558

 

思路

注意 0 不能放在第 1 位，所以如果每 1 位，先打一个除 0 以外最小的数，这个数的数量减 1，再打出剩余所有数。

 

代码

#include <stdio.h>

int main()
{
    int a[10] = {0};
    for(int i = 0; i < 10; i++) scanf("%d", &a[i]);
    // 处理前面的 0 
    if(a[0])
    {
        for(int i = 1; i < 10; i++)
            if(a[i]){
                printf("%d", i);
                a[i]--;
                break;
            }
    }

    for(int i = 0; i < 10; i++)
    {
        while(a[i]--) {printf("%d", i);}
    }

    return 0;
}

改进

看了别人写的代码以后，发现我对oj系统有一定的误解，我每次都是一次性输完，然后将数存储在数组或其他结构中，然后再做运算。
其实可以一边输入，一边计算的，如果对结果没有影响的话。

#include <stdio.h>

int main()
{
    // 设置一个数来记录 0 的数量  
    int zero = 0, notzero = 0;
    scanf("%d", &zero);
    for(int i = 1; i <= 10; i++)
    {
        scanf("%d", &notzero);
        while(notzero--)
        {
            putchar('0' + i);
            while(zero-- > 0) putchar('0');
        }
    }
    return 0;
}

// 先输出一个除0的数，再把所有的 0 都输出
// 然后再输出剩下的数

注意点

检测zero的时候本来是这样写的：

while(notzero--)
        {
            putchar('0' + i);
            while(zero) putchar('0');
        }

但是发现会出现死循环，然后这样检测一下：

#include <stdio.h>

int main()
{
    int zero = 0, notzero = 0;
    scanf("%d", &zero);
    int j = 0;
    for(int i = 1; i <= 10; i++)
    {
        scanf("%d", &notzero);
        while(notzero--)
        {
            putchar('0' + i);
            while(zero-- > -10) 
            {
                printf("zero = %d\n", zero);
                putchar('0');
             }
        }
    }
    return 0;
}

输出结果：

2 2 0 0 0 3 0 0 1 0
1zero = 1
0zero = 0
0zero = -1
0zero = -2
0zero = -3
0zero = -4
0zero = -5
0zero = -6
0zero = -7
0zero = -8
0zero = -9
0zero = -10
015558

如果仅仅是检测zero是否为 0 ，zero在下一个循环还会继续循环下去。