九度 OJ 1146 煎餅排序：貪心翻轉算法詳解

題目規則

對長度 N 的排列，允許「前綴翻轉」操作：選擇位置 k，將前 k 個元素逆序。要求在 2N-3 步內排序完成，輸出操作序列。

貪心策略

每輪固定當前最大元素到最終位置：

1. 找到最大值位置 pos
2. 若 pos ≠ 1，翻轉前 pos 個 → 最大值移到首位
3. 翻轉前 i 個（i 為目標位置） → 最大值歸位

每輪最多 2 次翻轉，共 N-1 輪 → 2N-2 步，滿足 2N-3 要求（最後一輪可優化）。

代碼實現

#include <cstdio>
using namespace std;

void flip(int *a, int k) {  // 翻轉前 k 個（1-based）
    for (int l = 1, r = k; l < r; l++, r--)
        swap(a[l], a[r]);
}

int main() {
    int n, a[31], ops[100], cnt;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        cnt = 0;
        for (int target = n; target >= 1; target--) {
            int pos = find(a+1, a+n+1, target) - a;
            if (pos == target) continue;  // 已在正確位置
            if (pos != 1) { flip(a, pos); ops[cnt++] = pos; }
            flip(a, target); ops[cnt++] = target;
        }
        printf("%d", cnt);
        for (int i = 0; i < cnt; i++) printf(" %d", ops[i]);
        puts("");
    }
    return 0;
}

關鍵細節

• 數組 1-based 索引，符合題目位置定義
• find 定位目標值當前位置
• 輸出格式：步數 + 空格分隔的操作位置序列