UVa 120 煎饼

https://vjudge.net/problem/UVA-120

题意：颠倒连续子序列，使之成为升序。

思路：按照从大到小的顺序，依次选择出一个数字进行分析：

①如果该数字已经在正确的位置上，则不用管。

②如果该数字已经在最顶端，则从它该在的位置一直到顶端颠倒。

③如果该数字不在最顶端，则应先把它搞到最顶端，再从它该在的位置一直到顶端颠倒。

 #include<iostream>

 #include<algorithm>

 #include<string>

 #include<cstring>

 #include<sstream>

 using namespace std;

 const int maxn = ;

 int ans[maxn];

 int coo[maxn];

 int coo2[maxn];

 int path[];

 int k;

 int num;

 string line;

 bool cmp(int a, int b)

 {

     return a > b;

 }

 void convert(int t)   //颠倒连续子序列

 {

     memcpy(coo2, ans, sizeof(ans));

     for (int i = ; i <= t; i++)

     {

         ans[i] = coo2[t - i + ];

     }

 }

 void solve()

 {

     memcpy(coo, ans, sizeof(ans));

     num = ;

     sort(coo + , coo + k + , cmp);

     for (int i = ; i <= k; i++)

     {

         int s = coo[i];

         if (ans[k-i+] == s) continue;  //如果已经在正确的位置上

         for (int j = ; j <= k; j++)

         {

             if (ans[j] == s)

             {

                 if (j != )  //如果未在顶端，先将它颠倒至顶端

                 {

                     convert(j);

                     path[num++] = k - j + ;

                 }

                 break;

             }

         }

         convert(k - i + );  //颠倒至正确位置

         path[num++] = i ;

     }

     path[num++] = ;

 }

 int main()

 {

     //freopen("D:\\txt.txt", "r", stdin);

     while (getline(cin,line    ))

     {

         k = ;

         int x;

         stringstream ss(line);

         while (ss >> x)  ans[++k] = x;

         for (int i = ; i <  k; i++)

             cout << ans[i] << " ";

         cout << ans[k] << endl;

         solve();

         for (int i = ; i < num - ; i++)

             cout << path[i] << " ";

         cout << path[num - ] << endl;

     }

     return ;

 }