Home PAT 1038 Recover the Smallest Number
Post
Cancel

PAT 1038 Recover the Smallest Number

正解

Link

事实证明, 这道题就是写得好痛苦…最难想到的地方就是那个比较函数了叭…

然后就好做了. 但是我还想多了: 题目的意思是说, 0 开头的数可以排在最前面, 只是 0 不用打印出来而已, 而我以为以 0 开头的数要化为最简形式 (即去掉前导 0) 之后才能排序, 同时还要保证不在第一个的数仍然保持其前导 0…

就是这个意思: 例如 0092 和 2934, 按照题目的意思, 它们的大小关系就是 0092 < 2934, 0092 仍然可以作为第一个数, 只是要打印成 92. 而我以为是, 2934 的第一个数是 2, 明显小于 92 中的 9 啊, 所以怎么能将 92 放在第一个呢…

先不说我的错误理解了, 总之最重要的就是那个比较函数, 可以写成 cmp 也可以重载运算符. 这里我作死用 C 字符串没用 string, 所以麻烦了许多, 不过又学到了一招: C 字符串的连接 qwq

比较函数:

1
2
3
bool cmp(string a,string b){
    return a+b<b+a;
}

看到有博客说和 UVA11729 Commando War 这题很相似, 等会儿看看…

AC 代码如下:

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n;
struct node{
    char num[10];
    bool operator<(node x)const{
        char tmp1[20],tmp2[20];
        strcpy(tmp1,num);
        strcpy(tmp1+strlen(tmp1),x.num);
        strcpy(tmp2,x.num);
        strcpy(tmp2+strlen(tmp2),num);
        return strcmp(tmp1,tmp2)<0;
    }
}a[10010];
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%s",a[i].num);
    sort(a+1,a+1+n);
    bool flag=false;
    for(int i=1;i<=n;++i){
        if(flag){printf("%s",a[i].num);continue;}
        int j=0;
        while(j<strlen(a[i].num)&&a[i].num[j]=='0') j++;
        if(j<strlen(a[i].num)){
            flag=true;
            printf("%s",a[i].num+j);
        }
    }
    if(!flag) printf("0");
    return 0;
}

题外话: C 字符串的连接

关于 C 字符串的连接, 可以用如下方法:

1
2
char s1[20]="Hello ",s2[10]="World!";
strcpy(s1+strlen(s1),s2);

注意, 如果上面代码中的 s1 没有赋初值, 那么它的长度是不确定的, 因此:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
char num1[10]="32",num2[10]="321";
char tmp1[20],tmp2[20]; //没有赋初值
cout<<strlen(tmp1)<<endl;
//所以说这里就不要strcpy(tmp1+strlen(tmp1),num2)了
strcpy(tmp1,num1);
cout<<strlen(tmp1)<<endl;
strcpy(tmp1+strlen(tmp1),num2);
cout<<strlen(tmp2)<<endl;
strcpy(tmp2,num2);
cout<<strlen(tmp2)<<endl;
strcpy(tmp2+strlen(tmp2),num1);
cout<<strlen(tmp1)<<endl;
cout<<strlen(tmp2)<<endl;
printf("%s %s\n",tmp1,tmp2);

拓展

虽然我的理解是错的, 但是我的代码在那种情形下还是对的…而且还比此题复杂一些:

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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n;
struct node{
    char num[10];
    char ch;
    bool operator<(node x)const{
        char tmp1[20],tmp2[20];
        strcpy(tmp1,num);
        strcpy(tmp1+strlen(tmp1),x.num);
        strcpy(tmp2,x.num);
        strcpy(tmp2+strlen(tmp2),num);
        return strcmp(tmp1,tmp2)<0;
    }
}a[10010];
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%s",a[i].num);
        int j=0;
        while(j<strlen(a[i].num)&&a[i].num[j]=='0') j++;
        if(j==0) a[i].ch=a[i].num[0];
        else if(j==strlen(a[i].num)) a[i].ch='0';
        else a[i].ch=a[i].num[j];
    }
    sort(a+1,a+1+n);
    char minv=':',idx=0;
    for(int i=1;i<=n;++i)
        if(a[i].ch!='0'&&a[i].ch<minv){
            minv=a[i].ch;
            idx=i;
        }
    if(idx==0){
        printf("0\n");
        return 0;
    }
    int j=0;
    while(j<strlen(a[idx].num)&&a[idx].num[j]=='0') j++;
    printf("%s",a[idx].num+j);
    for(int i=1;i<=n;++i)
        if(i!=idx)
            printf("%s",a[i].num);
    printf("\n");
    return 0;
}
This post is licensed under CC BY 4.0 by the author.