UVa 120 煎饼

 1 #include<iostream>  
 2 #include<algorithm>
 3 #include<string>
 4 #include<cstring>
 5 #include<sstream>
 6 using namespace std;
 7 
 8 const int maxn = 35;
 9 int ans[maxn];
10 int coo[maxn];
11 int coo2[maxn];
12 int path[1000];
13 int k;
14 int num;
15 
16 string line;
17 
18 bool cmp(int a, int b)
19 {
20     return a > b;
21 }
22 
23 void convert(int t)   //颠倒连续子序列
24 {
25     memcpy(coo2, ans, sizeof(ans));
26     for (int i = 1; i <= t; i++)
27     {
28         ans[i] = coo2[t - i + 1];  
29     }
30 }
31 
32 void solve()
33 {
34     memcpy(coo, ans, sizeof(ans));
35     num = 0;
36     sort(coo + 1, coo + k + 1, cmp);
37     for (int i = 1; i <= k; i++)
38     {
39         int s = coo[i];
40         if (ans[k-i+1] == s) continue;  //如果已经在正确的位置上
41         for (int j = 1; j <= k; j++)
42         {
43             if (ans[j] == s)
44             {
45                 if (j != 1)  //如果未在顶端，先将它颠倒至顶端
46                 {
47                     convert(j);   
48                     path[num++] = k - j + 1; 
49                 }
50                 break;
51             }
52         }
53         convert(k - i + 1);  //颠倒至正确位置
54         path[num++] = i ;
55     }
56     path[num++] = 0;
57 }
58 
59 int main()
60 {
61     //freopen("D:\\txt.txt", "r", stdin);
62     while (getline(cin,line    ))
63     {
64         k = 0;
65         int x;
66         stringstream ss(line);
67         while (ss >> x)  ans[++k] = x;
68         for (int i = 1; i <  k; i++)
69             cout << ans[i] << " ";
70         cout << ans[k] << endl;
71         solve();
72         for (int i = 0; i < num - 1; i++)
73             cout << path[i] << " ";
74         cout << path[num - 1] << endl;
75     }
76     return 0;
77 }