uva 120 Stacks of Flapjacks
题意：给出一个长度为n的序列（无重复元素），询问经过多少次flip(i)操作，使得序列升序排列。定义flip(i)为将1到n-i+1的元素反转… 思路：先离散化，然后注意读入….
1/* ***********************************************
2Author :111qqz
3Created Time :2016年01月25日 星期一 10时42分46秒
4File Name :code/uva/120.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=105;
34int n;
35int a[N];
36string in;
37
38struct node
39{
40 int value;
41 int id;
42}q[N];
43int pos[N];
44bool cmp1(node a,node b)
45{
46 return a.value<b.value;
47}
48bool cmp2(node a,node b)
49{
50 return a.id<b.id;
51}
52
53
54void flip2( int x)
55{
56 for ( int i = 1 ; i <= x/2 ; i++)
57 {
58 swap(q[i].value,q[x+1-i].value);
59 }
60}
61
62void print( int n)
63{
64 for ( int i = 1 ; i <= n ; i ++) printf(" %d ",q[i].value);
65 printf("\n");
66}
67
68void getpos( int n)
69{
70 for ( int i = 1 ; i <= n ; i++)
71 {
72 pos[q[i].value] = i;
73 }
74}
75int main()
76{
77 #ifndef ONLINE_JUDGE
78 freopen("code/in.txt","r",stdin);
79 #endif
80
81 while (getline(cin,in))
82 {
83 ms(pos,-1); //pos[i]表示数字i的位置
84 // cout<<"oriin:"<<in<<endl;
85 int p = in.find(' ');
86 int val;
87 int cnt = 0 ;
88 while (p!=-1)
89 {
90
91 string tmp = in.substr(0,p);
92 sscanf(tmp.c_str(),"%d",&val);
93 in.erase(0,p+1);
94 p = in.find(' ');
95 // cout<<"in:"<<in<<endl;
96 cnt++;
97 a[cnt] = val;
98 }
99 sscanf(in.c_str(),"%d",&val);
100 cnt++;
101 a[cnt]=val;
102
103 for ( int i = 1 ; i <= cnt ; i++) cout<<a[i]<<" ";
104 cout<<endl;
105 //hash
106 for ( int i = 1 ; i <= cnt ; i++)
107 {
108 q[i].value = a[i];
109 q[i].id = i ;
110 }
111
112 sort(q+1,q+cnt+1,cmp1);
113 int hashnum = 0;
114 for ( int i = 1 ; i <=cnt ; i++)
115 {
116 hashnum++;
117 q[i].value = hashnum;
118 }
119 sort(q+1,q+cnt+1,cmp2);
120
121 //check hash
122// for ( int i =1 ; i <= cnt ; i++) cout<<"q[i].val:"<<q[i].value<<" ";
123
124
125 for ( int i = 1 ; i <= cnt ; i++)
126 {
127 pos[q[i].value] = i ;
128 }
129
130 // print(cnt);
131 for ( int i = cnt ; i >=1 ; i--)
132 {
133 if (pos[i]==i) continue;
134 if (pos[i]==1)
135 {
136 printf("%d ",cnt+1-i);
137 flip2(i);
138 // print(cnt);
139 getpos(cnt);
140
141 }
142 else
143 {
144 printf("%d ",cnt+1-pos[i]);
145 flip2(pos[i]);
146 // print(cnt);
147 getpos(cnt);
148 printf("%d ",cnt+1-i);
149 flip2(i);
150 // print(cnt);
151 getpos(cnt);
152 }
153 }
154 puts("0");
155
156
157
158 }
159
160
161 #ifndef ONLINE_JUDGE
162 fclose(stdin);
163 #endif
164 return 0;
165}