題目敘述
在一個叫「堆疊市」的城市中有一個著名的火車站。由於地形限制以及經費關係，火車站及唯一的鐵路的樣子如下圖：
現在火車從A方向來，預定從B方向離開。火車共有N節車廂，並且各車廂依次以1到N來編號。你可以假設各車廂在進站之前可以單獨與其他車廂分離，也可以單獨離開車站到往B方向的鐵軌或是車站北方的「維修鐵路」上。維修鐵路是一小段至多只能容納M節車廂的鐵軌，可以從車站依照順序將車廂移至維修鐵路，或者將車廂從維修鐵路（如果有的話）駛進車站，但是在把車廂從A開進車站的時候，維修鐵路不能有任何車廂。你可以假設在任何時間火車站都可以容納所有的車廂。但是一旦一節車廂進站後，就不能再回到A方向的鐵軌上了，並且一旦離開車站往B方向後，也不能再回到車站。
現在你的任務是寫一個程式，判斷火車能否以一特定的排列方式在B方向的鐵軌上。
輸入說明
第一行有兩個正整數 $N, M$。($1\le N\le 1000, 0\le M\le 9$)
第二行有 $N$ 個正整數，為 $1, 2, \ldots, N$ 的一個排列。
輸出說明
若能在 B 鐵軌上排出特定排列，請輸出 yes，否則請輸出 no。
Sample Input
5 1
3 2 5 1 4
Sample Output
yes
出處
95建中資訊培訓模擬試題一（Prob 4）
OJ連結
題解
這題有個決定性的觀察：基本上，當一節火車從 A 進入車站時，他所排列的位置必須在所有已經進入車站的車廂最上面。也就是說，無論哪些車廂已經被送到鐵軌 B 處，從上到下的順序永遠是遞減的（與進入車站的順序相反），剛好是一個堆疊的樣子。
於是這讓我們能用基於貪婪法的模擬來解題：如果要駛出的車廂出現在目前堆疊頂端 $M+1$ 節車廂裡面，那我們就直接把他開走。如果想要的車廂還沒有進到車站，就不斷放車廂進來，直到該節車廂一進站立馬停下來。
/* by tmt514 */
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N, M, x, now = 0;
vector<int> station;
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> x;
// 不斷把新的車廂放進來，直到目標車廂出現為止。
while (now < x) station.push_back(++now);
// 計算目標車廂的位置。
auto it = find(station.begin(), station.end(), x);
int dist = station.end() - it;
if (dist > M+1) {
// 距離過遠代表得放超過 M 個車廂到上面，做不到。
cout << "no" << endl;
return 0;
} else {
// 否則就模擬把這節車廂開走。
station.erase(it);
}
}
cout << "yes" << endl;
return 0;
}
關於這題
這一題的原始構想是來自於 [UVa 514] Rails，只不過加上了一條維修鐵路，所以變得有一點不太相同，但解法還是差不多。