120-Stacks of Flapjacks

<br /> /* <br /> "Stacks of Flapjacks"<br /> Level:5.5<br /> Date:2007/5/29<br /> 技巧：<br /> input:利用getline讀入字串，再用strtok()將空白清除。<br /> process:<br /> 1.將最大的元素先reverse至top of stack<br /> 2.再將top of stack reverse到bottom<br /> 3.將次大元素reverse至top of stack<br /> 4.再將top of stack reverse到bottom-1<br /> repeat...until (bottom ==1)<br /> <br /> Bill Gaze大一寫的論文，就是提出多種Flapjacks problem及解法，<br /> 後來主要被應用在生物資訊的DNA字串比對。<br /> */<br /> <br /> #include <iostream><br /> #include <vector><br /> #include <algorithm><br /> #include <string><br /> <br /> using namespace std;<br /> <br /> int main(){<br /> string str;<br /> char *s, *str2char;<br /> vector<int> ivec;<br /> vector<int>::iterator iter;<br /> vector<int>::iterator iter_end;<br /> vector<int>::iterator spatula; //要翻的煎餅，翻的位置要+1, <br /> <br /> int max; //暫存bottom以上最大的element. <br /> int bottom; //bottom以上皆未排序. <br /> <br /> while(getline(cin,str)){<br /> str2char = new char[str.size()+1];<br /> strcpy(str2char, str.c_str()); <br /> ivec.clear();<br /> <br /> //將input string清掉空白,並一一丟入int array <br /> for(s = strtok(str2char, " "); s!= NULL; s=strtok(NULL, " ")){<br /> ivec.push_back(atoi(s));<br /> }<br /> iter = ivec.begin();<br /> iter_end = ivec.end();<br /> <br /> bottom = ivec.size(); <br /> cout << str << endl; while(1){ if(bottom ==1){ cout << "0" << endl; break; } iter = ivec.begin(); //如果top element是最大者,便從bottom以上做reverse,並將bottom向上移動一層 if(ivec[0] == (max = *max_element(iter, iter+bottom))){ if(ivec[0] == ivec[bottom-1]){ --bottom; continue; } reverse(iter, iter+bottom); cout << ivec.size()-bottom+1 << " "; --bottom; } /*否則從bottom以上找最大元素，並從最大元素下做reverse， *以將最大元素移至top element. */ else{ spatula = find(iter, iter+bottom, max); /*如果最大元素正好在bottom的上方， *便無須reverse，並將bottom向上移動一層. */ if(ivec[spatula-iter] == ivec[bottom-1]){ --bottom; continue; } reverse(iter, spatula+1); cout << ivec.size() - (spatula-iter) << " "; } } } }