首页 > 代码库 > 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 (摊煎饼。。)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。