[高效算法 deque运用]UVa120 - Stacks of Flapjacks

[高效算法 deque运用]UVa120 - Stacks of Flapjacks

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 #include #include #include #include #include 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。