北京北站现有 n 节车厢从 A 方向驶入，并按进站顺序依次编号，站长要求这些车厢按照指定的顺序从 B 方向使出。Qingyong从《交通运输概论》课程学习到，完成站长的任务需要借助中转站（记为 C 方向）。假设 C 可以停放任意数量的车厢，但是 C 末端封闭，因此，驶入 C 站的车厢必须按照相反的顺序驶出。 Qingyong进一步限定允许的操作如下：

让 A 方向最前面的车厢从 B 方向驶出车站；
让 A 方向最前面的车厢驶入中转站 C；
让中转站 C 中最后驶入的车厢从 B 方向驶出车站。
请帮助Qingyong判断能否让车厢按照站长给定的顺序驶出北京北站。

输入数据
第一行为一个正整数 n，代表车厢总数，n < 100000。 第二行有 n 个正整数，代表站长要求的车厢驶出车站顺序。

输出数据
Yes或者No

连输入输出示例都没给出，那我劝题主别浪费时间做这种题目了。
不管布置这道作业给你的老师是存心刁难你而不肯给（失德），还是粗心大意忘了给（失职），都是在浪费别人的时间。

当然这道题本身是很简单的，对于任意一个数，小于其值的数应该在其右边以从大到小的顺序排列。
比如 2 4 1 3 中 4 后面小于4的数列 { 1， 3 } 不是按从大到小的顺序排列，所以它就是不可能的顺序。
因为 4 在 1、3 之前驶出，那么 1、3 就得按顺序先进入中转站等待，出站顺序就必然是 3 在 1 之前。

故有代码

#include <stdbool>

bool check( const size_t buf[], size_t n )
{
    for( size_t i=0; i!=n; ++i )
    {
        size_t cur_min = buf[i];
        for( size_t j=i+1; j!=n; ++j )
        {
            if( buf[j] < cur_min )
                cur_min = buf[j];
            else if( buf[j] < buf[i] )
                return false;
        }
    }
    return true;
}

优化了一下，10万个车厢的情况下速度快了5万倍。
bool check2(const int *buf, int n)
{   
    //假设顺序编号从0开始累加
    int tmpBuf[100000];
    int i, j, num;

    if (n<0 || n>100000)
    {
        printf("Error 1\n");
        return false;
    }

    for (i=0; i<n; i++)
    {
        if (buf[i]<0 || buf[i]>n)
        {
            printf("Error 2\n");
            return false;
        }
    }

    tmpBuf[0] = -1;
    for (i=n-1, j=n-1, num=0; i>=0; )
    {
        if (buf[i] == j)
        {
            j--;
            i--;
            continue;
        }

        if (tmpBuf[num] == j)
        {
            j--;
            num--;
            continue;
        }

        num++;
        tmpBuf[num] = buf[i];
        i--;
    }

    for (; num>=0; j--,num--)
    {
        if (tmpBuf[num] != j)
        {
            printf("No\n");
            return false;
        }
    }

    printf("Yes\n");
    return true;
}

收到的鲜花

• rjsp 于 2021-07-21 14:32 送鲜花  10朵