UVa 120 - Stacks of Flapjacks

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址
中文網址
利用翻轉數列來達到由小到大，4321 -> 1234。

Solution

從最底層開始處理，依序push進stack(這裡我使用vector)

ex.

(top) 5 3 6 2 1 4 (bottom)

[5]  5  
[4]  3  
[3]  6  
[2]  2  
[1]  1  
[0]  4

i = 0
從[ i ]開始尋找上面是否有比[ i ]大的數(取較大的):

• 有，將較大的數~Top翻轉，再從[ i ]~Top進行翻轉即可將[ i ]變為較大的數。
• 沒有，繼續。

最後 i + 1
重複直到 i 到 Top。

P.S.輸出翻轉的位置為stack的index+1。

Code

UVa 120UVa 120 - Stacks of Flapjacks

#include<cstdio>
#include<vector>
#include<algorithm>

int main()
{
    int cake[30] = {}, flip_pos[50] = {}, i;
    char str[150];

    while (gets(str))
    {
        //input token
        int count = 0, num = 0, flip = 0;
        for (i = 0; str[i]; i++)
        {
            if (str[i] != ' ')
                num = num * 10 + str[i] - '0';
            else
            {
                cake[count++] = num;
                num = 0;
            }
        }
        cake[count++] = num;

        std::vector<int> v;
        //cake[0] is top
        for (i = count - 1; i >= 0; i--)
            v.push_back(cake[i]);

        //v[0] is bottom
        for (i = 0; i < count; i++)
        {
            int max = v[i], pos = 0;
            for (int j = i + 1; j < count; j++)
                if (max < v[j])
                {
                max = v[j];
                pos = j;
                }

            //底部的flip pos為1
            if (pos)
            {
                //較大的在頂部，則不用轉
                if (pos != count - 1)
                {
                    std::reverse(v.begin() + pos, v.end());
                    flip_pos[flip++] = pos + 1;
                }

                std::reverse(v.begin() + i, v.end());
                flip_pos[flip++] = i + 1;
            }
        }

        //output
        puts(str);
        for (i = 0; i < flip; i++)
            printf("%d ", flip_pos[i]);
        puts("0");

    }

    return 0;
}