d550: 物件排序

2019-08-30

內容

Excel 的排序，使用上真是有點麻煩
現在請你先對第一列先做排序，
若還是相同，再比較第二列 …類推 ( 由小 → 大)

輸入

每組輸入的第一行會有兩個數字 N M ( 1 ≦ N ≦ 1,0000 , 1 ≦ M ≦ 200 )

分別代表接下來有 N 行 , 每行上有 M 個數字 P ( 0 ≦ P ≦ 2147483647 )

8 3
1 1 2
1 0 1
1 1 1
1 3 2
1 3 5
2 1 1
2 3 2
2 1 4

輸出

請輸出排序後的結果。

1 0 1
1 1 1
1 1 2
1 3 2
1 3 5
2 1 1
2 1 4
2 3 2

解題思路

簡單的逐個比較排序，本題重點在於如何提升排序速度。

將輸入的資料存入一個二微陣列 L，再用一個一維指標陣列 S 去指向 L 的開頭，如此一來排序時只要交換 S[i] 指標指向的位置就能表示整個陣列 L[i] 的互換。

本題輸入輸出量很大，可以考慮做 IO 優化。

完整程式碼

正常版

AC (0.4s, 7.9MB)

#include <stdio.h>
#include <stdlib.h>
#define ROW 10000
#define COL 200

int n, m, list[ROW][COL], * sort[ROW];

int cmp(const int** lhs, const int** rhs)
{
    for (int i = 0; i < m; i++)
    {
        if ((*lhs)[i] > (*rhs)[i])
            return 1;
        else if ((*lhs)[i] < (*rhs)[i])
            return -1;
    }
    return 0;
}

int main()
{
    for (int i = 0; i < ROW; i++)
        sort[i] = list[i];
    while (scanf(" %d %d", &n, &m) == 2)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                scanf(" %d", &list[i][j]);
        }
        qsort(sort, n, sizeof(int*), cmp);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                printf("%d ", sort[i][j]);
            putchar('\n');
        }
    }
    return 0;
}

IO 優化版

AC (0.1s, 8.9MB)

#include <stdio.h>
#include <stdlib.h>
#define BUFSIZ 1048576
#define ROW 10000
#define COL 200

int n, m, list[ROW][COL], * sort[ROW];

inline char readChar()
{
    static char buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;
    if (now == end)
    {
        if (end < buffer + BUFSIZ)
            return EOF;
        end = (buffer + fread(buffer, 1, BUFSIZ, stdin));
        now = buffer;
    }
    return *now++;
}

inline char readUInt(unsigned int* dst)
{
    register char ch;
    while ((ch = readChar()) < '0')
        if (ch == EOF) return 0;
    *dst = ch ^ '0';
    while ((ch = readChar()) >= '0')
        * dst = (*dst << 3) + (*dst << 1) + (ch ^ '0');
    return 1;
}

int cmp(const int** lhs, const int** rhs)
{
    for (int i = 0; i < m; i++)
    {
        if ((*lhs)[i] > (*rhs)[i])
            return 1;
        else if ((*lhs)[i] < (*rhs)[i])
            return -1;
    }
    return 0;
}

void putUInt(register int src, const char suffix)
{
    char buf[12], * bufTop = buf + 10;
    register int div;
    buf[10] = suffix, buf[11] = 0;
    do
    {
        *--bufTop = src - ((div = src / 10) << 3) - (div << 1) + '0';
    } while (src = div);
    fputs(bufTop, stdout);
}

int main()
{
    for (int i = 0; i < ROW; i++)
        sort[i] = list[i];
    while (scanf(" %d %d", &n, &m) == 2)
    {
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                readUInt(&list[i][j]);
        }
        qsort(sort, n, sizeof(int*), cmp);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
                putUInt(sort[i][j], ' ');
            putchar('\n');
        }
    }
    return 0;
}