UVA 400 Unix ls 命令模擬：格式化輸出文件名列表

問題描述

模擬 `ls` 輸出：給定 n 個文件名（長度 ≤ 60），按字典序排序，按列輸出。列寬 = 最長文件名長度 + 2（最後一列不加 2）。列數盡可能多（總寬 ≤ 60）。行數 = ceil(n / 列數)。按**列優先**順序輸出（即第 1 列前 r 個，第 2 列次 r 個...）。

算法步驟

1. 讀入文件名，記錄最大長度 `maxLen`。
2. 排序（`qsort` + `strcmp`）。
3. 計算列數 `cols = 60 / (maxLen + 2)`（至少 1）。
4. 計算行數 `rows = (n + cols - 1) / cols`。
5. 輸出 60 個 `-` 分隔線。
6. 雙重循環：外層行 `i=0..rows-1`，內層列 `j=0..cols-1`。索引 `idx = j * rows + i`。若 `idx < n` 輸出該文件名，補齊空格（最後一列補到 `maxLen`，其他補到 `maxLen+2`）。

代碼 (C)

#include 
#include 
#define MAXN 110
#define MAXL 65
char name[MAXN][MAXL];

int cmp(const void *a, const void *b) {
    return strcmp((char*)a, (char*)b);
}

void print_name(int idx, int width) {
    printf("%s", name[idx]);
    for (int i = strlen(name[idx]); i < width; ++i) putchar(' ');
}

int main() {
    int n;
    while (~scanf("%d", &n)) {
        int maxLen = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%s", name[i]);
            maxLen = max(maxLen, (int)strlen(name[i]));
        }
        qsort(name, n, MAXL, cmp);
        int cols = 60 / (maxLen + 2);
        int rows = (n + cols - 1) / cols;
        for (int i = 0; i < 60; ++i) putchar('-');
        putchar('\n');
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                int idx = j * rows + i;
                if (idx >= n) continue;
                if (j == cols - 1) print_name(idx, maxLen);
                else print_name(idx, maxLen + 2);
            }
            putchar('\n');
        }
    }
    return 0;
}

關鍵細節

• 列優先索引公式 `idx = j * rows + i` 是核心。
• 最後一列寬度不加 2，需單獨處理。
• 輸入多組測試，直到 EOF。
• 文件名可能包含大小寫、數字、點，`strcmp` 直接按 ASCII 排序符合字典序。

總結

UVA 400 考察排序、格式化輸出、二維索引映射。列優先遍歷是關鍵，寬度計算需仔細處理邊界。代碼簡短但易出 off-by-one 錯誤，建議多測邊界情況（n=1, n=60 等）。