Analysis 分析 算法很简单，给你一组煎饼，用笔在纸上一画就知道该怎么办了。还是动态规划的思想，从底至上，保持已经遍例过的煎饼都是最大且有序的。比如输入的数据为： 2 4 1 3
Analysis
分析
算法很简单，给你一组煎饼，用笔在纸上一画就知道该怎么办了。还是动态规划的思想，从底至上，保持已经遍例过的煎饼都是最大且有序的。比如输入的数据为：
2 4 1 3 5
按题目要求，4在顶5在底。5已经是最大的了，则移动到上一个煎饼3。3之上（含）最大的是4，先将4翻转到最顶，形成：
4 2 1 3 5
然后将4到3的子叠翻转，形成：
3 1 2 4 5
移动到上一个煎饼2，2之上（含）最大的是3，而3就在顶部，因此直接将2到3翻转，形成：
2 1 3 4 5
最后将2和1翻转，就完成了。注意：一定不要忘了在输入的一行数据下再将原数据复制输出一行，漏掉必然WA。按照上面的算法来做就不会出现多余的翻转操作，因此不用担心。
Solution
解答
#include <algorithm>
#include <iostream>
#include <iterator>
#include <deque>
#include <string>
#include <sstream>
using namespace std;
//主函数
int main( void ) {
//循环处理输入的每组字符串。每次循环一轮要输出最后的0和换行
for (string strLine; getline(cin, strLine); cout << '0' << endl) {
//按要求回应输入的字符串行
cout << strLine << endl;
//构造字符串流，以遍转换为数字
istringstream iss(strLine);
//将字符串转为数字，逆序(最底的在最前)存储在Stack里
deque< int > Stack;
for ( int nDiam; iss >> nDiam; Stack.push_front(nDiam));
//从底依次上向进行翻转，保持i上面的都比i小
for (deque< int >::iterator i = Stack.begin(); i != Stack.end(); ++i) {
//找出i上面(包括i)的最大元素
deque< int >::iterator iMax = max_element(i, Stack.end());
//如果最大元素就是i则继续(将i指向上面一个)
if (iMax != i) { //否则要进行需翻转操作
//如果最大的不在最上面，则需先翻转到最上面
if (iMax != Stack.end() - 1) {
reverse(iMax, Stack.end());
//输出翻转的起点
cout << distance(Stack.begin(), iMax) + 1 << ' ' ;
}
//将最大的从最上面翻转到i的位置上
reverse(i, Stack.end());
//输出翻转的起点
cout << distance(Stack.begin(), i) + 1 << ' ' ;
}
}
}
return 0;
}