The Water Problem——桶排序思想

港控/mmm° 2022-06-16 02:45 201阅读 0赞

Think:  
1数值位数可用数组表示，思考可否运用桶排序思想

[sdut题目链接][sdut]

The Water Problem  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
给定n个5位数字，分别把百位上相同的数按样例格式从小到大摆在一起。  
简单来说，就是按照百位上的数字输出一个表单，例如12345的百位是3，就放在3的后面，最后依次输出0-9后面所有的数字。

Input  
多组输入。  
输入数据占两行，每组数据的第一行是一个正整数n（<= 500），第二行有n个5位正整数。

Output  
如题目样例所示输出，每行最后记得输出一个-1作为行结束标志。

Example Input  
2  
12345 56389

Example Output  
0: -1  
1: -1  
2: -1  
3: 12345 56389 -1  
4: -1  
5: -1  
6: -1  
7: -1  
8: -1  
9: -1

Hint

Author  
2015级《程序设计基础II》计科软件通信期末上机考试2

以下为Accepted代码

#include <stdio.h>
    #include <string.h>
    
    int a[14][100000];
    
    int main()
    {
        int n, i, j, t, x;
        while(scanf("%d", &n) != EOF){
        
            memset(a, 0, sizeof(a));
            for(i = 0; i < n; i++){
        
                scanf("%d", &x);
                t = (x/100)%10;
                a[t][x]++;
            }
            for(i = 0; i <= 9; i++)
            {
        
                printf("%d:", i);
                for(j = 10000; j < 100000; j++){
        
                    while(a[i][j]--)
                        printf(" %d", j);
                }
                printf(" -1\n");
            }
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 416ms
    Take Memory: 1532KB
    Submit time: 2017-05-03 16:06:52
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2160/pid/3529