NYOJ 1057 尋找最大數（三）：貪心交換相鄰數位構造最大值

問題描述

給整數 N (≤10¹⁸) 和 K (≤100)。每次可交換相鄰兩位數字，最多 K 次。求能得到的最大整數。

貪心策略

從最高位開始，對於當前位 i，在剩餘交換次數 K 允許的範圍內（i 到 i+K），找到最大的數字，將其「冒泡」移動到位置 i，消耗 (pos - i) 次交換。更新 K，繼續下一位。
這相當於：在 K 步內能調動的窗口中選最大數字前移。

代碼實現 (C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s; int K;
    while (cin >> s >> K) {
        int n = s.size();
        for (int i = 0; i < n && K > 0; ++i) {
            // 在 [i, min(n-1, i+K)] 找最大數字及其最左位置
            char maxc = s[i];
            int maxpos = i;
            for (int j = i+1; j < n && j <= i+K; ++j) {
                if (s[j] > maxc) { maxc = s[j]; maxpos = j; }
            }
            // 將 maxpos 移動到 i
            for (int j = maxpos; j > i; --j) swap(s[j], s[j-1]);
            K -= (maxpos - i);
        }
        cout << s << '\n';
    }
    return 0;
}

複雜度

• 時間：O(n × K) 最壞，但 n ≤ 19 (10¹⁸), K ≤ 100，實際極快。
• 空間：O(n)。

關鍵點

• 貪心選擇：每步在可達範圍內取最大數字前移，證明最優（交換相鄰等價於冒泡排序，最大數字越前越大）。
• 字符串操作避免大整數溢出。
• 交換次數精確扣減，K 耗盡即停止。

這是「限制交換次數下的最大排列」問題，貪心 + 模擬冒泡是標準解法，代碼簡潔高效。