小M的调度
测试数据来自 system/1036
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
时间限制:1秒 内存限制:256M
【问题描述】
小M新应聘到列车调度员的工作,他每天的任务就是“按指定的顺序重组车厢”:车站有一个中转站 \(C\),这是一个最多可以停放 \(m\) 节车厢的车站,但由于末端封顶,驶入 \(C\) 的车厢必须按照相反的顺序驶出 \(C\)。有 \(n\) 节车厢按车厢按编号 \(1,2,…,n\) 的顺序从通道 \(A\) 驶入 \(C\),通过 \(C\) 的调度,按指定顺序 \(a_1,a_2,…,a_n\) 进入通道 \(B\)。对于每节车厢,一旦从 \(A\) 移入 \(C\),就不能再回到 \(A\) 了;一旦从 \(C\) 移入 \(B\),就不能回到 \(C\) 了。换句话说,任意时刻,只有两种选择:\(A->C\) 和 \(C->B\)。
最麻烦的事情就是判定进入 \(B\) 通道的顺序 \(a_1,a_2,…,a_n\) 是否可行。小M觉得编个程序来做这事会让自己变得轻松,于是请你来帮忙!
【输入格式】
第 1 行包含两个整数 \(n\) 和 \(m\),\(n\) 表示有 \(n\) 节车厢,\(m\) 表示中转站 \(C\) 最多能停放 \(m\) 节车厢。
第 2 行有 \(n\) 个整数 \(a_1,a_2,…,a_n\),是 \(1..n\) 的排列,表示指定的 \(B\) 通道驶出的车厢顺序。
【输出格式】
若 \(B\) 通道出站车厢顺序不可行输出"No",若可行,则输出"Yes"。
【输入输出样例1】
Input
6 3
2 4 3 6 5 1
Output
Yes
【输入输出样例1说明】
要实现 \(B\) 通道的顺序2,4,3,6,5,1,则中转站C按“1进、2进、2出、3进、4进、4出、3出、5进、6进、6出、5出、1出”的调度,可实现 \(B\) 通道出站顺序。
【输入输出样例2】
Input
6 2
2 4 3 6 5 1
Output
No
【数据限制】
对于100%的数据:\(1≤n≤100000\)。
【来源】
Mr.he