uva-10152 ShellSort

2016年07月12日 |

acm

| acm

• 题目：
• 代码：
• 解析&吐槽：

题目：

10152 - ShellSort
Time limit: 3.000 seconds

代码：

#include <iostream>
#include <queue>
#include <functional>
#include <vector>
#include <string>
#include <set>

using namespace std;

string L[10000];
string M[10000];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T;
    cin>>T;

    while(T--)
    {
        int n;
        cin>>n;

        getline(cin,L[0]);

        for(int i=0;i<n;++i)
            getline(cin,L[i]);
        for(int i=0;i<n;++i)
            getline(cin,M[i]);

        set<string> have;

        int pL=n-1,pM=n-1;

        while(pL >=0 &&pM >= 0 && have.find(M[pM]) == have.end())
        {
            if(L[pL]==M[pM])
            {
                --pL;
                --pM;
            }
            else
            {
                have.insert(L[pL]);
                --pL;
            }
        }

        while(pM>=0)
        {
            cout << M[pM--]<<endl;
        }

        cout <<endl;
    }
    return 0;
}

解析&吐槽：

一群乌龟叠成一叠，每一只都有一个不同的名字。现在要把这些乌龟排成指定的顺序，排序方式是固定 的：从中选出一只乌龟，让它爬到最上面。问选出乌龟的顺序是怎么样的。

分析一下排序的方式，我们可以发现如下规律：

1. 起始顺序和终止顺序中，最底下的乌龟如果顺序不变，就可以不予考虑
2. 只要有乌龟从下面爬上来，这只乌龟的目标位置上方的乌龟即使顺序不变， 稍后也必须要向上爬，因为下面的乌龟只能爬到最上面，这只乌龟必须要向上爬才能到达自己原来的位置。

因此我们只需要从下向上找，设置两个指针来表示我们目前在起始顺序和终止顺序中处理的乌龟。 如果当前的乌龟相同，就将两个指针同时上移；每找到一只在起始顺序中出现，但是终止顺序中没有的 乌龟，就把它放进一个 set 里面，同时起始顺序的指针上移，终止顺序的指针不变。直到找到一个 在终止顺序中出现在 set 里面的乌龟——说明这只乌龟是从下面爬上来的最靠下的乌龟。这时候它 上面的所有乌龟都是必须要重排顺序的（见规律 2），而它下面的乌龟则不需要排序，因为抽出所有 在 set 中的乌龟之后，下面的乌龟和终止顺序的乌龟顺序是一样的。因此我们只需要按照从下往上的 顺序输出它上面的所有乌龟即可。