题解 | Flipping Pancake

我是菜狗

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, num, pos;    // pos存放第k大的数idx的下标
    while (scanf("%d", &n) != EOF) {
        if (!n) continue; // 如果n为0，跳过当前循环

        vector<int> vec;
        vector<int> dis;
        vec.push_back(0);   // 保证数组从1开始存放
        int cnt = 0;        // 表示所有数需要反转的次数

        // 输入数组
        for (int i = 0; i < n; i++) {
            scanf("%d", &num);   // 数字是1-n
            vec.push_back(num);
        }

        // 煎饼排序
        for (int idx = n; idx >= 1; idx--) {
            // 判断是否在最终位置上
            if (vec[idx] == idx) {
                continue;
            }
            else {
                // 找到当前最大值的下标
                for (int i = 1; i <= n; i++) {
                    if (vec[i] == idx) {
                        pos = i;
                        break;
                    }
                }

                // 如果最大值不在最上面，翻转1到pos(如果最大值在最前面，则少一次翻转)
                if (pos != 1) {
                    reverse(vec.begin() + 1, vec.begin() + pos + 1);
                    dis.push_back(pos);
                    cnt++;
                }

                // 翻转1到idx，将最大值放到正确位置
                reverse(vec.begin() + 1, vec.begin() + idx + 1);
                dis.push_back(idx);     // 每次翻转的次数与距离都要记录
                cnt++;
            }
        }

        // 输出结果
        printf("%d", cnt);
        for (auto it = dis.begin(); it != dis.end(); it++) {
            printf(" %d", *it);
        }
        printf("\n");
    }
    return 0;
}