UVa 120 - Stacks of Flapjacks(构造法)

给出原本煎饼的排序,输出使得煎饼从小到大排列的翻煎饼方式。

翻煎饼就相当于颠倒序列中的一段连续子序列,每次都把没排好的需要排列在最下面的那个煎饼翻上来,然后再翻到相应的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<sstream>
using namespace std;
vector<int> a,b;
bool cmp(int x,int y){
return x>y;
}
void reverse(int n){
for(int i=0;i<(n+1)/2;++i) swap(a[i],a[n-1-i]);
return;
}
bool read(){
string s;
a.clear(),b.clear();
getline(cin,s);
stringstream ss(s);
int k,first=1;
while(ss>>k){
if(first) first=0;
else cout<<" ";
cout<<k;
a.push_back(k);
}
if(!a.size()) return false;
cout<<endl;
b=a;
return true;
}
int main(){
ios::sync_with_stdio(false);
while(read()){
int n=(int)a.size();
sort(b.begin(),b.end(),cmp);
for(int i=0;i<n;++i){
int j=0;
for(j=0;j<n;++j)
if(a[j]==b[i]) break;
if(j==n-1-i) continue;
else if(j){
cout<<n-j<<" "<<i+1<<" ";
reverse(j+1);
reverse(n-i);
}
else{
cout<<i+1<<" ";
reverse(n-i);
}
}
cout<<"0"<<endl;
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。

支付宝扫码领红包