UVA 10602 Editor Nottoobad：字符串排序後貪心計算最少按鍵次數

題目大意

編輯器操作：輸入字符 (press)、複製 (copy)、刪除。給定 n 個字符串，求輸入所有字符串所需的最少 press 次數。可任意調整輸入順序。

核心洞察

將字符串字典序排序後，相鄰字符串公共前綴最長。輸入順序按排序後順序，每個新字符串只需輸入與前一個字符串不重疊的後綴部分。

算法流程

1. 讀入 n 個字符串
2. 按 ASCII 碼升序排序 (標準字典序)
3. 第一個串全輸入：cost = len(s[0])
4. 對每個後續串 s[i]：找與 s[i-1] 的最長公共前綴長度 LCP，cost += len(s[i]) - LCP
5. 總 cost 即答案

完整 C++ 代碼

#include 
#include 
#include 
using namespace std;

const int MAXN = 105;
struct Word { char s[MAXN]; } w[MAXN];

bool cmp(const Word& a, const Word& b) {
    return strcmp(a.s, b.s) < 0;
}

int lcp(const char* a, const char* b) {
    int i = 0;
    while (a[i] && a[i] == b[i]) i++;
    return i;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%s", w[i].s);
        sort(w, w+n, cmp);
        
        int ans = strlen(w[0].s);
        for (int i = 1; i < n; i++)
            ans += strlen(w[i].s) - lcp(w[i-1].s, w[i].s);
        
        printf("%d\n", ans);
        for (int i = 0; i < n; i++) printf("%s\n", w[i].s);
    }
    return 0;
}

貪心策略證明

• 最優子結構：最優序列的任意前綴也是最優的
• 貪心選擇性質：當前狀態下，選擇與已輸入串 LCP 最長的下一個串，能最大化復用
• 排序等價性：字典序排序使相鄰串 LCP 之和最大化（類比最小生成樹中 Prim 算法）

關鍵細節

複雜度分析

• 排序：O(n log n · L) L=字符串長度
• LCP 計算：O(n · L)
• 總體：O(n log n · L)，n≤100 極快

樣例驗證

Input:
1
3
abc
abd
xyz

排序: abc, abd, xyz
cost = 3 + (3-2) + (3-0) = 7
操作序列:
abc (3 press)
abd: copy "ab", press 'd' (1 press)
xyz: press 'x','y','z' (3 press)
總計 7 press

總結

UVA 10602 是字符串貪心經典題。核心技巧：字典序排序最大化相鄰公共前綴。這一思想廣泛應用於：字典树構建、壓縮算法、版本控制差異計算、DNA 序列比對等領域。代碼簡短但需深刻理解貪心正確性證明。