[原创]杭电HDU 4550 字符串处理

2015-12-13 21:57:53 Tabris_ 阅读数：339

博客爬取于2020-06-14 22:45:18
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50287091

** 卡片游戏 **

** Time Limit: 3000/1000 MS(Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1675    Accepted Submission(s): 488
**

** Problem Description **

小明最近宅在家里无聊，于是他发明了一种有趣的游戏，游戏道具是N张叠在一起的卡片，每张卡片上都有一个数字，数字的范围是0~9，游戏规则如下：
首先取最上方的卡片放到桌子上，然后每次取最上方的卡片，放到桌子上已有卡片序列的最右边或者最左边。当N张卡片全部都放到桌子上后，桌子上的N张卡片构成了一个数。
这个数不能有前导0，也就是说最左边的卡片上的数字不能是0。游戏的目标是使这个数最小。
现在你的任务是帮小明写段程序，求出这个最小数。

** Input **

第一行是一个数T，表示有T组测试数据；
然后下面有T行， 每行是一个只含有0~9的字符串，表示N张叠在一起的卡片，最左边的数字表示最上方的卡片。

[Technical Specification]
T<=1000
1 <= N <= 100

** Output **

对于每组测试数据，请在一行内输出能得到的最小数。

** Sample Input **

3

565

9876543210

9876105432

** Sample Output **

556

1234567890

1678905432

主要思想就是模拟排一下序，把第一个数最为输出的第一个数（暂时的），然后进行比较，

看代码注释比较好  但一定注意含0的情况   坑点就是这个0.

有0的话第一个数就应该非0最小值，且排序的话之排序非0最小值之前的，之后的只能按输入的顺序放在后面（注释解释的更加详细）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
//=================================本人AC代码
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char a[102];
char b[300];  //排列用
int  main()
{
    int  t;
    scanf("%d", &t);
    getchar();
    while (t--)
    {
        memset(a, '\0', sizeof(a));
        memset(b, '\0', sizeof(b));
        gets(a);
        int  la  = strlen(a);
        int  tou = 150, wei = 150;
        int  f = 0, tt = 0;
        char mini;
        for (int i = 0; i < la; i++)
               //标记最小值用的  切记提议来说0是不可以的
            {
                if (a[i] != '0')
                {
                    mini = a[i];
                    break;
                }
            }
        for (int i = 0; i < la; i++)
        {
            if (a[i] == '0')
                f++;
            if (a[i] <= mini && a[i] != '0')
            {
                mini = a[i];
                tt   = i;
            }  //非0最小值
        }
        if (f == 0)
        {
            b[tou] = a[0];
            for (int i = 1; i < la; i++)
                   //其实就是左边和右边  如果这个数字比头数字大就放
                //后面  其他的发前面
                {
                    if (b[tou] >= a[i])
                    {
                        tou--;
                        b[tou] = a[i];
                    }
                    else
                    {
                        wei++;
                        b[wei] = a[i];
                    }
                }
            for (int i = tou; i <= wei; i++)
                printf("%c", b[i]);
            printf("\n");
        }
        else if (tt != 0)
        {
            b[tou] = a[0];
               //0不在首位那就以a[0]为标准来比较判断a[i]应该放在前面还//是后面
                printf("%c", a[tt]);
            for (int i = 1; i < tt; i++)
            {
                if (b[tou] >= a[i])
                {
                    tou--;
                    b[tou] = a[i];
                }
                else
                {
                    wei++;
                    b[wei] = a[i];
                }
            }
            for (int i = tou; i <= wei; i++)
            {
                if (i == tt)
                    continue;
                printf("%c", b[i]);
            }
            for (int i = tt + 1; i < la; i++)
                printf("%c", a[i]);
            printf("\n");
        }
        else
        {
            for (int i = 0; i < la; i++)
                    //如果存在0 且最小值在 首位  那么就不用排序了  //直接输出就可以了  为保证树最小那么一定要报
                    非零的最小值放在最前面 而根据题意  //数字就只能放到后面了 一个一个的 所以相当于没排序
                        printf("%c", a[i]);
            printf("\n");
        }
    }
}