车厢排序

一列火车有n个车厢标记为1，2，3，4，5，6…n
现在因为某些原因，需要调整车厢的相对顺序
例如需要将车厢顺序调整为2，3，1，4，5，6…n
由于车厢庞大，且车厢只能停留在铁轨上，所以不能随心所欲的调整相对顺序

现在只能利用两条并行的铁轨对车厢的顺序进行调整
例如
原序列为1，2的车厢
车厢1进入铁轨1停止
车厢2进入铁轨2，然后再开出
然后铁轨1上的车厢1再开出
这样可以使得车厢2调整到车厢1得前面

现在给你一个期望得到的车厢顺序，请你判断该顺序能否通过以上方法调整车厢顺序而得到
（车厢只能前进无法后退）
输入格式
第一行n表示有n个车厢
第二行有n个数为1~n的排列用空格隔开，表示期望得到的车厢顺序

输出：若可以得到则输出Yes 否则输出No

样例输入1：
2
2 1
样例输出1：
Yes

样例输入2：
5
3 4 1 5 2
样例输出2：
Yes

样例输入3：
5
3 4 2 1 5
样例输出3：
No

---

个人分析：

比如样例输入2：
5
3 4 1 5 2
样例输出2：
Yes

图解题意：

这里写图片描述

车厢1、2进入铁轨2，车厢3、4、5进入铁轨1，铁轨就像队列一样，先进先出

这里写图片描述

车厢5先停留下来，铁轨2的车厢1先行开出：

这里写图片描述

然后车厢5先出，车厢2最后开出即可。

而样例输入3：
5
3 4 2 1 5
样例输出3：
No

开始

这里写图片描述

车厢1、2进入铁轨2，车厢3、4、5进入铁轨1，铁轨就像队列一样，先进先出

这里写图片描述

然而车厢3、4车厢出来之后，车厢2无法开出，所以这个顺寻不可行：

这里写图片描述

故不可以做到，输出No。

# coding: utf-8

from collections import deque
def feasible(a, b):
    q1 = deque()
    q2 = deque()

    def find(x):
        for q in [q1, q2]:
            if q and q[0] == x:
                q.popleft()
                return True
        if not a or x < a[0]:
            return False
        if all((q1, q2)):
            return False

        q = filter(None, [q1, q2])
        if not q:
            q = q1

        i = x - a[0]            
        q.extend(a[:i])
        del a[:i+1]
        return True
    for x in b:
        if not find(x):
            return False
        
    return True


print feasible(range(1, 6), [3, 4, 2, 1, 5])
print feasible(range(1, 6), [3, 4, 1, 5, 2])