首页 > 代码库 > UVA - 120Stacks of Flapjacks (摊煎饼。。)

UVA - 120Stacks of Flapjacks (摊煎饼。。)

/*

这题使我记起了以前很多忘掉的东西,例如sstream(分割流),deque(双端队列),还有众多函数(STL里的)。值得收藏

值得注意的是这题的序号问题,(因为要求输出翻转的位置),序号从右往左为1-n;

*/

题目大意:

一摞煎饼,煎饼有直径这一属性,从下往上摞,遗憾的是英文看不懂,他给的样例从左往右,表示从上到下。保证按题中所给算法(反转某一位置之上的所有煎饼)使得最后的序列为从小到大排列;

解题思路:

题中所给算法如下例:

2 3 4 1  5  -->1 2 3 4  5

5应该在最后一位,所以2 3  4 1 5不翻转;

检查2位置,不为次小值,寻找此位置之前最大的数 --4  找到后观察其位置是否为顶部,不是顶部将其反转到顶部     4 3 2 1 5

然后将此位置为顶部交换得到1 2 3 4 5;

(若是顶部则直接将顶部与当前位置交换)具体做法则使用双端队列(ps:看到题目为stack一度想用栈),逆序存储,那么队列顶部就是这摞的底部,遍历即可;

 

代码:

#include<iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include<set>
#include <cstdio>
#include<iterator>
#include <sstream>
#include <cmath>
#include <deque>
using namespace std;


int main()
{
    string line;
    for (;getline(cin,line);cout<<"0"<<endl)  //这个操作使我眼前一亮,简单但是很有用因为他最后要输出一个0(虽然并不用这么做)
    {
        int x;
        int max_=0;
        int length=0;
        int zzzzz=0;
        stringstream ss(line);        //被我遗忘的流分割操作,输入一行进行切割;
        deque<int >p;              //定义双端队列
        while (ss>>x)
        {
            length++;
            if (max_<x) max_=x;
if (zzzzz==0) { cout<<x; zzzzz=1; } else cout<<" "<<x; p.push_front(x); //把数逆向输入队列。 } cout<<endl; deque<int >::iterator it; for (it=p.begin(); it!=p.end(); it++) { //cout<<"asdas"<<endl; deque<int >::iterator max_pos; max_pos=max_element(it,p.end()); if (it!=max_pos) { if(max_pos!=p.end()-1) { reverse(max_pos,p.end()); cout<<distance(p.begin(),max_pos)+1<<" "; } reverse(it,p.end()); cout<<distance(p.begin(),it)+1<<" "; } } } }

PS:

 

UVA - 120Stacks of Flapjacks (摊煎饼。。)