Codeforces 486C Palindrome Transformation：貪心構造回文最小操作數

Codeforces 486C Palindrome Transformation：貪心構造回文最小操作數

長度 n 的字符串，光標初始位置 p。操作：左右移動光標（循環）、上下修改字符（循環 a-z）。求構造回文的最小操作數。

問題分解

1. 字符修改代價：對每對 (i, n-i+1)，計算使其相等的最小上下鍵次數
2. 光標移動代價：訪問所有需修改的位置對，最小化移動距離

字符修改代價計算

對字符 a, b：

cost = min( abs(a-b), 26 - abs(a-b) )

累加所有不匹配對的 cost 為 `char_cost`。

光標移動最優策略

只需考慮左半部分 [1, n/2] 中需修改的位置。設這些位置為 L₁ < L₂ < ... < Lₖ。

光標初始在 p。若 p > n/2，映射到對稱位置 n-p+1。

最優路徑：從 p 出發，覆蓋 [L₁, Lₖ] 區間的最小移動：

if (k == 0) move_cost = 0;
else if (p <= L₁) move_cost = Lₖ - p;
else if (p >= Lₖ) move_cost = p - L₁;
else move_cost = min( 2*(p-L₁) + (Lₖ-p), 2*(Lₖ-p) + (p-L₁) );

完整算法流程

1. 讀入 n, p 和字符串 s (1-indexed)
2. 若 n==1 輸出 0
3. 計算所有不匹配對的字符修改代價，記錄左半部位置
4. 對左半部位置排序
5. 根據 p 計算光標移動代價
6. 答案 = char_cost + move_cost

C++ 參考實現

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, p; cin >> n >> p;
    string s; cin >> s;
    s = " " + s; // 1-indexed
    
    if (n == 1) { cout << 0 << "\n"; return 0; }
    
    vector<int> positions;
    long long char_cost = 0;
    
    for (int i = 1; i <= n/2; ++i) {
        int j = n - i + 1;
        if (s[i] != s[j]) {
            int diff = abs(s[i] - s[j]);
            char_cost += min(diff, 26 - diff);
            positions.push_back(i);
        }
    }
    
    if (positions.empty()) { cout << 0 << "\n"; return 0; }
    
    // 映射光標到左半部
    if (p > n/2) p = n - p + 1;
    
    int L = positions.front(), R = positions.back();
    long long move_cost;
    if (p <= L) move_cost = R - p;
    else if (p >= R) move_cost = p - L;
    else move_cost = min(2*(p-L) + (R-p), 2*(R-p) + (p-L));
    
    cout << char_cost + move_cost << "\n";
    return 0;
}

樣例驗證

n=8, p=3, s=aeabcaez
配對: (1,8) a-z cost=1
      (2,7) e-e cost=0
      (3,6) a-a cost=0
      (4,5) b-c cost=1
char_cost = 2
positions = [1, 4]
p=3 (已在左半部)
L=1, R=4, p=3 ∈ [1,4]
move_cost = min(2*(3-1)+(4-3), 2*(4-3)+(3-1)) = min(5, 4) = 4
總計 = 2 + 4 = 6 ✓

關鍵洞察總結

1. 字符修改與光標移動獨立優化
2. 只需處理左半部，右半部對稱
3. 光標移動本質是覆蓋區間 [L, R] 的最短路徑
4. 循環字符串/光標移動通過映射簡化

複雜度

• 時間：O(n)
• 空間：O(n)
• n ≤ 1e5，線性極快

此題展示了將複雜操作分解為獨立子問題、利用對稱性簡化、區間覆蓋最短路徑等經典技巧的綜合運用。