Codeforces 486C Palindrome Transformation：貪心構造回文（C題單獨詳解）

Codeforces 486C Palindrome Transformation：貪心構造回文（C題單獨詳解）

長度 n 字符串，光標初始位置 p (1-indexed)。操作：左右移動光標(循環)、上下修改字符(循環 a-z)。最小操作數使字符串變回文。

問題分解

1. 字符修改代價：每對 (i, n-i+1) 需變相同，代價 = 循環距離
2. 光標移動代價：訪問所有需修改位置的最小移動

字符修改代價

diff = abs(s[i] - s[j]);
cost = min(diff, 26 - diff);

光標移動最優策略

只需處理左半部位置 [1, n/2]。設需修改位置為 L₁ < L₂ < ... < Lₖ。
光標初始 p，若 p > n/2 映射到對稱位置 n-p+1。

覆蓋區間 [L₁, Lₖ] 的最小移動：

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

完整代碼

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

bool can(int m, int s) { return s >= 0 && 9*m >= s; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int m, s; cin >> m >> s;
    if (!can(m, s)) { cout << "-1 -1\n"; return 0; }
    if (m == 1) { 
        if (s >= 10) cout << "-1 -1\n"; 
        else cout << s << " " << s << "\n"; 
        return 0;
    }
    if (s == 0) { cout << "-1 -1\n"; return 0; }
    
    string min_s, max_s;
    int sum = s;
    // 最小數
    for (int i = 1; i <= m; ++i) {
        for (int d = (i==1?1:0); d <= 9; ++d) {
            if (can(m-i, sum-d)) { min_s += '0'+d; sum -= d; break; }
        }
    }
    // 最大數
    sum = s;
    for (int i = 1; i <= m; ++i) {
        for (int d = 9; d >= 0; --d) {
            if (can(m-i, sum-d)) { max_s += '0'+d; sum -= d; break; }
        }
    }
    cout << min_s << " " << max_s << "\n";
    return 0;
}

樣例驗證

Input: 2 15
最小: 首位試1→剩1位需14不可(>9)；試2→剩13不可...試6→剩9可→69
最大: 首位試9→剩6可→96
Output: 69 96

Input: 3 0 → -1 -1 (m>1且s=0無解)

關鍵洞察

1. 字符修改與光標移動獨立優化
2. 左半部位置排序後，光標移動轉化為覆蓋區間問題
3. 循環字符串/光標通過映射簡化為線性問題
4. 貪心構造最小/最大數：最小數高位盡可能小(但首位≥1)，最大數高位盡可能大

複雜度

• 時間：O(n + m×10) = O(n)
• 空間：O(n)

此題綜合考察字符串操作、貪心策略、循環結構處理、構造算法，是 Codeforces Div2 C 級別的優質題目。