火车调度

Description

有一个火车站，铁路如图所示，每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n≤1000），分别按照顺序编号为1，2，3，…，n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨，它就不能再回到车站C。

负责车厢调度的工作人员需要知道能否使它以a1,a2,…,an的顺序从B方向驶出，请来判断能否得到指定的车厢顺序。

Input
第一行为一个整数n，其中n≤1000，表示有n节车厢，第二行为n个数字，表示指定的车厢顺序。

Output
如果可以得到指定的车厢顺序，则输出一个字符串“YES”，否则输出“NO

先上代码：

 1 #include<iostream>
 2 using namespace std;
 3 int a[1001];
 4 int top;
 5 int b[1001];
 6 int main()
 7 {
 8     int n;
 9     cin>>n;
10     for(int i=1;i<=n;i++)
11     {
12         cin>>a[i];
13     }
14     for(int i=1,head=0;i<=n;i++)
15     {
16         while(a[i]>head)
17         {
18             b[++top]=++head;
19         }
20         if(a[i]==b[top])
21         {
22             top--;
23         }
24         else 
25         {
26             cout<<"NO";
27             return 0;
28         }
29     }
30     cout<<"YES";
31     return 0;
32 }

啥意思呢？

不是输入了一串数表示他们的先后顺序吗，我们依靠这个已知条件先正推再反推，先正推：

输入了a[1]，那我们就必须把小于a[1]的数全都压进栈中，再让栈顶出栈，接下来输入的是a[2]，如果a[2[小于栈顶元素，那我们就不可能让这个调度成立对吧，因为它上面的元素肯定会比他先出栈，所以直接输出no并return 0就好了，如果大于栈顶元素，那就将小于a[2]的还没有被调用过的数压入栈中，并输出栈顶元素，如果a[i]等于栈顶元素，就直接出栈就可以了。

总结一下就是：将小于a[i]的所有元素压入栈中，再将栈顶元素pop掉，但如果栈顶元素无法满足等于a[i]，那肯定就无解了，直接return就好了，

拜拜

2022/3/17