codeup-大整数排序

2023-11-23 10:20:40

Problem E: 大整数排序

Time Limit: 1 Sec Memory Limit: 32 MB
Submit: 433 Solved: 198
[Submit][Status][Web Board][Creator:Imported]

Description

对N个长度最长可达到1000的数进行排序。

Input

输入第一行为一个整数N，(1<=N<=100)。
接下来的N行每行有一个数，数的长度范围为1<=len<=1000。
每个数都是一个正数，并且保证不包含前缀零。

Output

可能有多组测试数据，对于每组数据，将给出的N个数从小到大进行排序，输出排序后的结果，每个数占一行。

Sample Input

Sample Output

123
1234
2345
12345


正确的通过OJ的代码如下：

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

struct bign{
    char d[1010];
    int len;
    bign(){
        memset(d, 0, sizeof(d));
        len = 0;
    }
};

bool cmp(bign a, bign b){
    if(a.len != b.len){
        return a.len<b.len;
    }else{
        return strcmp(a.d, b.d)<0;
    }
}

int main(){
    vector<bign> vb;
    bign vn;
    int n;
    while(scanf("%d", &n) != EOF){
        vb.clear();
        for(int i=0; i<n; i++){
            scanf("%s", vn.d);
            vn.len = strlen(vn.d);
            vb.push_back(vn);
        }
        sort(vb.begin(), vb.end(), cmp);
        for(int i=0; i<n; i++){
            printf("%s\n", vb[i].d);
        }
    }
    return 0;
}


这里主要讨论使用sort时，写cmp函数时应注意的问题：
可以看到通过编译时的cmp是这样的：

bool cmp(bign a, bign b){
    if(a.len != b.len){
        return a.len<b.len;
    }else{
        return strcmp(a.d, b.d)<0;
    }
}

但是如果我把else部分改为以下形式，则OJ会给出50%的错误：

bool cmp(bign a, bign b){
    if(a.len != b.len){
        return a.len<b.len;
    }else{
        return !strcmp(a.d, b.d);
    }
}

这是因为，strcmp返回的值有三类：正数、0、负数，strcmp前面取反，因此只有当a.d与b.d这两个char字符数组相等时，才会返回cmp才会返回true。这显然不合题意了。

可是，最让我郁闷的不是这个问题，而是我一开始写的cmp函数，如下：

bool cmp(bign a, bign b){
    if(a.len != b.len){
        return a.len<b.len;
    }else{
        bool flag = true;
        for(int i=0; i<a.len; i++){
            if(a.d[i]>b.d[i]){
                flag = false;
                break;
            }
        }
        return flag;
    }
}

自己在else部分写了一个比较两个字符数组大小的逻辑，一旦a.d[i]>b.[i]出现，就可以认为前者大于后者，返回false。但是在OJ编译时，一直给出50%的错误。不明白原因何在？？？（暂且存疑）

除了用字符串来存储整数外，其实还可以采用string来存储。此时cmp函数应该写成如下形式：

bool cmp(string a, string b){
    if(a.size() != b.size()){
        return a.size() < b.size();
    }else{
        return a < b;
    }
}

码农公寓