煎饼排序问题题解

一、题目分析

题目要求通过翻转操作将煎饼堆栈排序，每次可翻转顶部k个煎饼，目标是找到最多2n-3次翻转的序列。关键规则：

• 输入为1到N的排列，表示煎饼大小（数字越大煎饼越大）；
• 输出翻转次数及每次翻转的k值，使堆栈变为“小顶大底”有序。

二、算法思路

1. 贪心策略：从最大的煎饼开始排序，每次将当前需要的煎饼（第i大）移动到正确位置（第i位）。
2. 翻转步骤：
   • 找到当前需要的煎饼（值为i）的位置pos；
   • 若pos≠1，先翻转前pos个煎饼，将其移动到顶部；
   • 再翻转前i个煎饼，将其移动到第i位（底部）。

三、代码实现（原代码框架）

#include<iostream>
#include<iomanip>
using namespace std;
#include<algorithm>
#include<math.h>
#include<string>
#include<vector>
#include<set>
#define MAX 128
int a[MAX];
int myfind(int x,int n) {
	for (int i = 1; i <= n; i++) 
		if (a[i] == x)return i;
	return 0;
}
int main() {
	ios::sync_with_stdio(false);
	
	int n;
	while (cin >> n) {
		if (n == 0)break;
		vector<int>v;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		for (int i = n; i >= 1; i--) {
			if (a[i] != i) {
				while (a[i] != i) {
					int pos = myfind(i,n);
					if (pos == 1) {
						v.push_back(i);
						reverse(a + 1, a + 1 + i);
					}
					else {
						v.push_back(pos);
						reverse(a + 1, a + 1 + pos);
						v.push_back(i);
						reverse(a + 1, a + 1 + i);
					}
					
				}
			}
			else {
				continue;
			}
		}
		cout << v.size()<<" " ;
		for (int i = 0; i < v.size(); i++)
			cout << v[i] << " ";
		cout << endl;
		
	}
	
	
	
	return 0;
}

四、代码核心逻辑解析

1. 查找函数myfind：

   • 在堆栈a[1..n]中遍历，返回值为x的煎饼位置，用于定位目标煎饼。

2. 主循环流程：

   • 逆向处理煎饼：从最大的煎饼（值为n）开始，依次处理到最小的煎饼（值为1）。
   • 定位目标煎饼：通过myfind(target, n)找到值为target的煎饼在堆栈中的位置pos。
   • 翻转操作：
     • 若pos≠1，先翻转前pos个煎饼，将目标煎饼移动到栈顶（reverse(a+1, a+1+pos)）；
     • 无论pos是否为1，都翻转前target个煎饼，将目标煎饼移动到第target位（栈底方向）。

3. 结果输出：

   • 用vector<int> flips存储所有翻转的k值，最后输出其大小和具体序列。

五、示例解析

输入：3 1 3 2（n=3，初始堆栈为[1, 3, 2]）

1. 处理target=3：
   • 目标煎饼值为3，当前位置pos=2；
   • 翻转前2个煎饼：reverse([1,3]) → 堆栈变为[3,1,2]，记录flips=[2]；
   • 翻转前3个煎饼：reverse([3,1,2]) → 堆栈变为[2,1,3]，记录flips=[2,3]。
2. 处理target=2：
   • 目标煎饼值为2，当前位置pos=1；
   • 翻转前2个煎饼：reverse([2,1]) → 堆栈变为[1,2,3]，记录flips=[2,3,2]。
3. 输出：3 2 3 2，共3次翻转，符合2n-3=3的上限。

六、复杂度分析

• 时间复杂度：O(n²)，每个煎饼最多需要2次翻转，每次翻转操作时间为O(k)（k≤n）。
• 空间复杂度：O(n)，存储煎饼堆栈和翻转序列。

七、关键技巧

1. 逆向贪心策略：从最大的煎饼开始排序，确保每次操作后大煎饼固定在底部，避免重复移动。
2. 两次翻转策略：通过“翻到栈顶→翻到目标位置”的组合操作，保证每个煎饼准确归位，且翻转次数≤2n-3。
3. 位置判断优化：若目标煎饼已在栈顶（pos=1），则省去一次翻转，直接将其翻到目标位置。