UVA-101 The Blocks Problem 栈模拟

终于AC了，这道题目去年寒假卡得我要死，最后一气之下就不做了。。。想想居然一年之久了，我本来都快忘了这道题了，最近发现白书的奥秘，觉得刘汝佳的题目真的相当练思维以及对代码的操作，决定又刷起题目来，这时候才想起这道题。

用栈进行模拟堆砖块，用个rec[]数组记录其现在所在的栈号，比较麻烦的是pile 操作，为了把a以及a以上的所有砖块都以原秩序放置于b砖块顶端，我用了个临时的栈进行存贮，然后再一个一个放到b栈上面。。这样就不会破坏秩序。。但是感觉这样做挺耗时的，原以为通不过，结果还是通过了。。。22ms，也不算太高吧。。不知道还有没有更好的pile方法

这个题目去年我都没想清楚题意，题目里面有个关键词 initial，意味着所有操作要还原的砖块都应该还原到它原本的位置，即 1还原到1号栈 2还原到2号栈，依次类推，因为根据题目的意思以及几大操作分析，一个栈要么就没元素，要么栈底元素就是栈号对应的元素，一旦移走了，栈必为空，一旦要还原，必定就把还原成最原始的样子

。一年了，觉得自己思维进步了一些，这是好事，继续加油！

#include <iostream>

#include <cstdio>

#include <cstring>

#include <stack>

#include <queue>

#define N 35

using namespace std;

stack <int> arr[N];

int rec[N];

int n,a,b;

char ch1[],ch2[];

void solve()

{

    int temp=arr[rec[a]].top();;

    int t2=arr[rec[b]].top();

    if (temp==t2) return;

    if (ch1[]=='m' && ch2[]=='n')

    {

        while (temp!=a)

        {

            arr[temp].push(temp);

            rec[temp]=temp;

            arr[rec[a]].pop();

            temp=arr[rec[a]].top();

        }

        while (t2!=b)

        {

            arr[t2].push(t2);

            rec[t2]=t2;

            arr[rec[b]].pop();

            t2=arr[rec[b]].top();

        }

        arr[rec[b]].push(a);

        arr[rec[a]].pop();

        rec[a]=rec[b];

        return;

    }

    if (ch1[]=='m' && ch2[]=='v')

    {

        while (temp!=a)

        {

            arr[temp].push(temp);

            rec[temp]=temp;

            arr[rec[a]].pop();

            temp=arr[rec[a]].top();

        }

        arr[rec[b]].push(a);

        arr[rec[a]].pop();

        rec[a]=rec[b];

        return;

    }

    if (ch1[]=='p' && ch2[]=='n')

    {

        while (t2!=b)

        {

            arr[t2].push(t2);

            rec[t2]=t2;

            arr[rec[b]].pop();

            t2=arr[rec[b]].top();

        }

        stack <int> q;

        while (temp!=a)

        {

            q.push(temp);

            arr[rec[a]].pop();

            temp=arr[rec[a]].top();

        }

        arr[rec[b]].push(temp);

        arr[rec[a]].pop();

        rec[a]=rec[b];

        while (!q.empty())

        {

            int tt=q.top();

            q.pop();

            rec[tt]=rec[b];

            arr[rec[b]].push(tt);

        }

        return;

    }

    if (ch1[]=='p' && ch2[]=='v')

    {

        stack <int> q;

        while (temp!=a)

        {

            q.push(temp);

            arr[rec[a]].pop();

            temp=arr[rec[a]].top();

        }

        arr[rec[b]].push(temp);

        arr[rec[a]].pop();

        rec[a]=rec[b];

        while (!q.empty())

        {

            int tt=q.top();

            q.pop();

            rec[tt]=rec[b];

            arr[rec[b]].push(tt);

        }

    }

}

void print()

{

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

    {

       printf("%d:",i);

       stack<int> q;

       while (!arr[i].empty())

       {

           int temp=arr[i].top();

           q.push(temp);

           arr[i].pop();

       }

       while (!q.empty())

       {

           printf(" %d",q.top());

           q.pop();

       }

       putchar('\n');

    }

}

int main()

{

    scanf("%d",&n);

    int i,j;

    for (i=;i<n;i++){

        arr[i].push(i);

        rec[i]=i;

    }

    getchar();

    while (scanf("%s",ch1))

    {

        if (ch1[]=='q')

            break;

        scanf("%d%s%d",&a,ch2,&b);

        getchar();

        solve();

    }

    print();

}

巴特西

UVA-101 The Blocks Problem 栈模拟

最新文章

热门文章