a528: 大數排序

2019-08-13

內容

排列數字一定很容易嗎

現在給你一堆數字

請你幫我排序

輸入

多筆測資

每筆測資第一行輸入一正整數 N

皆下來的 N 行每行有一個整數 Xi (1 <= i <= N)

（0 < N < 1000, | Xi | < 10¹⁰⁰)

5
1
3
2
5
0
4
222222222222222222222222222
111111111111111
-44444444444444444444444444444444444444444444444444444
33333333333333333333333333333333333333333333

輸出

將排序好的數字由小到大分行輸出

範例如下

0
1
2
3
5
-44444444444444444444444444444444444444444444444444444
111111111111111
222222222222222222222222222
33333333333333333333333333333333333333333333

解題思路

定義一個結構

typedef struct node
{
int Length;
char Num[110];
}BigNum;

輸入時將大數字串存入 Num ，並將其長度存入 Length 。
如果 Num[0] 為 ‘-‘ 則將 Length 改為 -Length 。

比較 BigNum 時，先比較 BigNum.Length 如果 BigNum.Length 一樣再用 strcmp() 比較 BigNum.Num 。

完整程式碼

AC (2ms, 220KB)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
    int Length;
    char Num[110];
}BigNum;

BigNum list[1000], * sort[1000];

int cmp(const BigNum** lhs, const BigNum** rhs)
{
    if ((*lhs)->Length != (*rhs)->Length)
        return (*lhs)->Length - (*rhs)->Length;
    return (*lhs)->Length < 0 ? strcmp((*rhs)->Num, (*lhs)->Num) : strcmp((*lhs)->Num, (*rhs)->Num);
}

int main()
{
    int n;
    while (scanf("%d", &n) == 1)
    {
        for (int i = 0; i < n; i++)
        {
            scanf(" %s", list[i].Num);
            list[i].Length = list[i].Num[0] == '-' ? -((int)strlen(list[i].Num)) : strlen(list[i].Num);
            sort[i] = &list[i];
        }
        qsort(sort, n, sizeof(BigNum*), cmp);
        for (int i = 0; i < n; i++)
            puts(sort[i]->Num);
    }
    return 0;
}