THU2017spring 2-2 Train 题解

THU2017spring 2-2 Train


描述

某列车调度站的铁道联接结构如图所示。

其中,A为入口,B为出口,S为中转盲端。所有铁道均为单轨单向式:列车行驶的方向只能是从A到S,再从S到B;另外,不允许超车。因为车厢可在S中驻留,所以它们从B端驶出的次序,可能与从A端驶入的次序不同。不过S的容量有限,同时驻留的车厢不得超过m节。

设某列车由编号依次为{1, 2, …, n}的n节车厢组成。调度员希望知道,按照以上交通规则,这些车厢能否以{a1, a2, …, an}的次序,重新排列后从B端驶出。

输入

共两行。

第一行为两个整数n,m。

第二行为以空格分隔的n个整数,保证为{1, 2, …, n}的一个排列,表示待判断可行性的驶出序列{a1,a2,…,an}。

输出

仅一行。若驶出序列可行,则输出Yes;否则输出No。

输入样例1

1
2
5 2
1 2 3 5 4

输出样例1

1
Yes

输入样例2

1
2
5 5
3 1 2 4 5

输出样例2

1
No

限制

1 <= n <= 100,000

0 <= m <= 100,000

时间:1 sec

空间:256 MB

提示

这题边界条件比MOOC卡的严多了,需要考虑0的情况:
也是栈混洗,把原来的代码搞过来的……(逃)

直接来代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<cstdio>
#include<cstring>
template <typename T> struct Stack{
    private:
        int _capacity;
        int _size;
        T * array;
    public:
        Stack(int capacity){
            this->array=new T[capacity];
            this->_capacity=capacity;
            this->_size=0;
        }
        ~Stack(){
            delete [] array;
        }
        bool empty(){
            return (_size==0);
        }
        bool full(){
            return (_size==_capacity);
        }
        int size(){
            return _size;
        }
        void push(T content){
            this->array[_size]=content;
            _size++;
        }
        void pop(){
            _size--;
        }
        T & top(){
            return array[_size-1];
        }
};
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    Stack<int> S(m);
    int * array=new int[n+1];
    for(int i=1;i<=n;i++)scanf("%d",array+i);
    int arrptr=1;
    if(m==0){
        for(int i=1;i<=n;i++){
            if(array[i]!=i){
                printf("No");
                return 0;
            }
        }
        printf("Yes");
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(!S.full()){
            S.push(i);
            while(!S.empty()&&array[arrptr]==S.top()){
                S.pop();
                arrptr++;
            }
        }else{
            printf("No");
            return 0;
        }
    }
    if(arrptr>n&&S.empty()){
        printf("Yes");
        return 0;
    }else{
        printf("No");
        return 0;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注