（队列思想+快排函数）—keke祝你元宵节快乐！

以你之姓@ 2022-07-12 05:44 169阅读 0赞

think:  
1题目首先输入一个字符串，然后根据6的位置可以把其前面的符合要求的字符串存放在一个队列里，当遇到6时候判断队列是否为空，若不为空则可以将其转化为实数存放在整型数组里面，以上只是6位于字符串中间以及末尾，还需要考虑的情况有  
1>6位于字符串第一位  
2>字符串最后一位不为6  
3>整个字符串只有一位  
2 将满足条件的数据存放在整型数组中之后，可以选择调用快排函数进行排序，尽量优化时间，避免时间超时  
3注意细节，尤其像数组的范围需要考虑临界条件进行判断，根据输入的字符串长度范围可以算得临界最多可以有333333个数，因此在定义整型数组的时候才可以尽量准确，不至于偏差太大，还有就是题意要求每组数据输出结束后输出一个空行，也是需要注意的

[sdut原题链接][sdut]

keke祝你元宵节快乐！  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
今天是元宵节，所以我们集训队的长者 (bLue) 决定在今天自掏腰包请大家吃汤圆。听到有免费的午餐，吃货们一个个跑得比西方的记者还要快，这也导致了场面十分混乱，所以长者决定将恢复排队队列有序这个光荣的任务交给你，希望你不要令长者失望！  
每个吃货都有一个长度不超过4位的序号，例如 “0807”, “15”, “007” 等等，由于人太多，我们并不知道有多少人在排队，只知道代表排队队列的一串由 ‘0’-‘9’ 组成的字符串，代表吃货们的序号，不同的吃货序号中间由一个或多个连续的字符 ‘6’ 分隔开，请从小到大输出吃货们的序号！

Input  
第一行输入一个组数 T (1 <= T <= 10)。  
每组输入一个字符串（长度不超过 666666），代表当时排队队列的字符串。

Output  
对于每组输入，先输出 “Case x:”（不包括引号）代表第几组。  
接下来一行请从小到大输出 K 个整数表示吃货的序号（不能有前导零）。  
每组末尾输出一个空行。

Example Input  
1  
1067810666666160674368467486666666

Example Output  
Case 1:  
0 1 10 84 743 748 7810

Hint  
示例解释：  
10 6 7810 666666 1 6 0 6 743 6 84 6 748 6666666  
10 7810 1 0 743 84 748

Author  
「2017年寒假集训 阶段测试赛2 - 元宵节专场」keke

以下为accepted代码

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    int top, flag, data[400000];
    char link[9], st[700000];
    int cmp(const void *a, const void *b)
    {
        return ((*(int *)a) - (*(int *)b));
    }
    int pow(int n, int m)
    {
        int ans = 1;
        while(m--)
        {
            ans *= n;
        }
        return ans;
    }
    int main()
    {
        int T, i, k, len, sum;
        scanf("%d", &T);
        getchar();
        for(k = 1; k <= T; k++)
        {
            top = flag = 0;
    
            scanf("%s", st);
            len = strlen(st);
    
            link[top++] = st[0];
            for(i = 1; i < len; i++)
            {
                if(st[i] != '6')
                {
                    link[top++] = st[i];
                }
                else if(st[i] == '6' && top != 0)
                {
                    sum = 0;
                    for(int j = 0; j < top; j++)
                    {
                        sum += (link[j]-'0')*pow(10, top-j-1);
                    }
    
                    data[flag++] = sum;
                    top = 0;
                }
            }
    
            if(st[len-1] != '6' || len == 1)
            {
                sum = 0;
                for(i = 0; i < top; i++)
                {
                    sum += (link[i]-'0')*pow(10, top-i-1);
                }
                data[flag++] = sum;
                top = 0;
            }
    
            qsort(&data[0], flag, sizeof(data[0]), cmp);
            printf("Case %d:\n", k);
            for(i = 0; i < flag; i++)
            {
                printf("%d%c", data[i], i == flag-1? '\n': ' ');
            }
            printf("\n");
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 296ms
    Take Memory: 3788KB
    Submit time: 2017-02-13 19:34:20
    ****************************************************/

以下为presentation error代码—每组数据结束后输出一个空行  
[百度：校内ACM上出现Presentation Error的一点经验][ACM_Presentation Error]

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    int top, flag, data[400000];
    char link[9], st[700000];
    int cmp(const void *a, const void *b)
    {
        return ((*(int *)a) - (*(int *)b));
    }
    int pow(int n, int m)
    {
        int ans = 1;
        while(m--)
        {
            ans *= n;
        }
        return ans;
    }
    int main()
    {
        int T, i, k, len, sum;
        scanf("%d", &T);
        getchar();
        for(k = 1; k <= T; k++)
        {
            top = flag = 0;
    
            scanf("%s", st);
            len = strlen(st);
    
            link[top++] = st[0];
            for(i = 1; i < len; i++)
            {
                if(st[i] != '6')
                {
                    link[top++] = st[i];
                }
                else if(st[i] == '6' && top != 0)
                {
                    sum = 0;
                    for(int j = 0; j < top; j++)
                    {
                        sum += (link[j]-'0')*pow(10, top-j-1);
                    }
    
                    data[flag++] = sum;
                    top = 0;
                }
            }
    
            if(st[len-1] != '6' || len == 1)
            {
                sum = 0;
                for(i = 0; i < top; i++)
                {
                    sum += (link[i]-'0')*pow(10, top-i-1);
                }
                data[flag++] = sum;
                top = 0;
            }
    
            qsort(&data[0], flag, sizeof(data[0]), cmp);
            printf("Case %d:\n", k);
            for(i = 0; i < flag; i++)
            {
                printf("%d%c", data[i], i == flag-1? '\n': ' ');
            }
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Presentation Error
    Take time: 300ms
    Take Memory: 3788KB
    Submit time: 2017-02-13 19:32:16
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/1997/pid/3793
[ACM_Presentation Error]: http://jingyan.baidu.com/article/29697b913e1e2aab20de3c0d.html