uva 120——Stacks of Flapjacks

妖狐艹你老母 2022-08-10 00:48 45阅读 0赞

题意：一个非常有趣的问题，就是给一摞煎饼，然后从下面拿起来一张，然后把该张上面的所有馅饼反转，求最后使得馅饼从小到大的最小的步数。

思路：贪心。每次都把没排好序的最大数反转到最上面，然后在一次反转到最下面，也就是最多需要2n步就能够把所有的馅饼排好。

Code：

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <string>
    #include <sstream>
    #include <cstring>
    #include <cmath>
    #include <map>
    #include <vector>
    #include <queue>
    #include <set>
    using namespace std;
    
    typedef long long ll;
    typedef unsigned long long ull;
    const int N=1000000;
    const int M=105;
    const int mod=10000007;
    const int INF=0x3f3f3f3f;
    const ll LINF=0x3f3f3f3f3f3f3f3f;
    const double eps=1e-9;
    const double pai=acos(-1.0);
    #define lson l,m,rt<<1
    #define rson m+1,r,rt<<1|1
    #define cls(x,c) memset(x,c,sizeof(x))
    #define fr(i,n) for (int i=0;i<n;i++)
    
    int a[35],len;
    int tran(int j)
    {
        int t=j;
        for (int i=0;i<j;i++)
            if (a[i]>a[t]) t=i;
        return t;
    }
    int main()
    {
        string s;
        int i,j;
        while (getline(cin,s))
        {
            if (s=="") break;
            cout<<s<<endl;
            stringstream ss;
            ss<<s;
            len=0;
            while (ss>>a[len]) len++;
            //fr (i,len) cout<<"bug2"<<a[i]<<endl;
            for (int i=len-1;i>=0;i--)
            {
                j=tran(i);
                //cout<<"bug  "<<j<<endl;
                if (j==i) continue;
                if (j!=0)
                {
                    printf("%d ",len-j);
                    reverse(a,a+j+1);
                }
                reverse(a,a+i+1);
                printf("%d ",len-i);
            }
            puts("0");
        }
    }