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
5 2
1 2 3 5 4
输出样例1
Yes
输入样例2
5 5
3 1 2 4 5
输出样例2
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; } } |