UVa 10602 - Editor Nottoobad 解題詳解

題目大意

有一台特殊編輯器，支援三種操作：輸入字符、複製、刪除。給定一組字串集合，求輸入這些字串所需的最少按鍵次數（僅計算「輸入字符」操作）。

核心觀察與策略

1. 排序優化：將所有字串依 ASCII 碼排序，使相鄰字串擁有最大公共前綴，從而最大化「複製」操作的效益。
2. 貪心計算：第一個字串必須全輸入（長度 L₀）；後續每個字串僅需輸入「與前一字串不同的後綴部分」。
3. 關鍵公式：總按鍵數 = L₀ + Σ(len[i] - LCP(i-1, i))，其中 LCP 為最長公共前綴長度。

演算法步驟

1. 讀入測資筆數 T
2. 對每筆測資：
   a. 讀入 n 及 n 個字串
   b. 以 strcmp 升冪排序字串陣列
   c. 計算首字串長度 + 累加後續字串「非共同前綴長度」
   d. 輸出最小按鍵數與排序後字串順序（題目允許任意最優解）

複雜度分析

• 排序：O(n log n * L)，L 為平均字串長度（≤100）。
• LCP 計算：O(n * L)。
• 整體極佳，滿足 UVa 時限。

參考實作（C++）

#include <bits/stdc++.h>
using namespace std;

struct Word { char s[105]; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n; cin >> n;
        vector<Word> w(n);
        for (int i = 0; i < n; ++i) cin >> w[i].s;
        sort(w.begin(), w.end(), [](const Word& a, const Word& b){
            return strcmp(a.s, b.s) < 0;
        });
        int ans = strlen(w[0].s);
        for (int i = 1; i < n; ++i) {
            int k = 0;
            while (w[i-1].s[k] && w[i-1].s[k] == w[i].s[k]) ++k;
            ans += strlen(w[i].s) - k;
        }
        cout << ans << '\n';
        for (auto &x : w) cout << x.s << '\n';
    }
    return 0;
}

常見誤區提醒

• ❌ 以為必須保持原始輸入順序 → 題目明確允許任意輸出順序，排序是關鍵。
• ❌ 忽略第一個字串必須完整輸入 → 答案初始值為首字串長度。
• ❌ LCP 計算未處理字串結束 → while (w[i-1].s[k] && ...) 確保不越界。

延伸思考

若操作成本不均勻（如複製成本 < 輸入成本），問題轉化為最短路徑/動態規劃，但本題等成本下貪心排序即為最優解。