題目鏈接：https://vjudge.net/problem/UVA-514

題目分析

題目的意思是給一個棧輸入一系列數據，在這個過程中可以出棧，看能否達到某個結果。
剛開始我覺得這個情況好多，因此不是用模擬，而應該觀察結果本身。對于結果中某個元素x，比他小的元素肯定已經入過棧了，此時可能有兩種去處：

1. 已經在結果里面了
2. 還在棧里面

對于1.，只能說它比x 小而且在x的前面，除此之外沒有其他約束了。
對于2.，那些比x小的元素在結果中的位置肯定在x的后面，而且肯定是逆序排列。因為只能進棧一次，而他們是從小到大進棧的，必然是從大到小出棧的。如果不符合這個條件肯定就是非法情況。
我的思路就是檢查每個元素后面比他小的元素是否是逆序的，復雜度是$O(n^2)$
UVa里面有時候要求最后有換行，有時候又要求不能有空行，真是讓人摸不著頭腦。。

AC代碼

#include <iostream>
#include <vector>
#include <deque>using namespace std;int n;
vector<int> arr;bool check_idx(int idx) {int x = arr[idx];int minx = x;for (int i = idx + 1; i < n; ++i) {if (arr[i] < x) {if (arr[i] > minx) return false;minx = arr[i];}}return true;
}bool check() {for (int i = 0; i < n; ++i) {if (!check_idx(i)) return false;}return true;
}bool first = true;int main() {ios::sync_with_stdio(false);while (cin >> n && n != 0) {
//        if (first) first = false;
//        else cout << "\n";arr.resize(n);while (cin >> arr[0] && arr[0] != 0) {for (int i = 1; i < n; ++i) cin >> arr[i];if (check()) cout << "Yes\n";else cout << "No\n";}cout << "\n";}return 0;
}

半年后再來寫這道題，還是想到了這種方法，雖然想到了一個優化，但是最壞的復雜度仍然是O(n^2)的。而且沒有用函數封裝，導致代碼丑了一些。
和上次一樣在換行這里卡了，UVa真惡心，還卡換行。

//
// Created by Administrator on 2022/4/20.
//#include <iostream>
#include <vector>/** 當x進入B的時候，C中都是比x小的元素，A中都是比x大的元素。* 因為進入C的元素越來越大，所以比x小的還未出現的元素肯定在C里面的，而且是以倒序出現在x的后面。* 因此對于出站的每一個x，判斷后面比x小的元素是不是逆序的。如果是則為真，以后訪問到就不用再判斷了，如果出現一個假就不可能了*/using namespace std;template<typename T>
void print(const vector<T> &arr) {for (auto &x : arr) cout << x << " ";cout << "\n";
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int n, t;vector<int> arr;vector<bool> illegal;bool fail;while (cin >> n && n) {arr.resize(n);illegal.resize(n, false);while (cin >> t && t) {for (int i = 0; i < n; ++i) illegal[i] = false;arr.clear();arr.push_back(t);for (int i = 1; i < n; ++i) {cin >> t;arr.push_back(t);}//print(arr);fail = false;for (int i = 0; i < n; ++i) {if (illegal[i]) continue;t = arr[i];illegal[i] = true;for (int j = i + 1; j < n; ++j) {if (arr[j] < arr[i]) {if (arr[j] < t) {illegal[j] = true;t = arr[j];} else {fail = true;break;}}}if (fail) break;}if (fail)  cout << "No\n";else cout << "Yes\n";}cout << "\n";}return 0;
}

更好的思路

看了一下書上了代碼（書上的代碼真的丑，寫出這么晦澀的代碼也是很厲害的），發現是可以進行模擬的，而且復雜度是$O(n)$，如果題目有心刁難我上面的解法可能就會TLE。
模擬的思路就是，剛開始肯定是按照從小到大的元素進棧，如果我們結果中當前元素直接是這個入棧的元素，那么再直接出棧，否則就丟在棧里。如果不是當前入棧元素，那么就和棧頂的元素比較，如果也不是，那就先入棧，看看后面的元素還有沒有希望，如果所有元素都已經入棧了，那就沒希望了，直接GG。

AC代碼

#include <iostream>
#include <vector>
#include <deque>using namespace std;int n;
deque<int> s;
vector<int> arr;bool check() {int x = 1;for (int i = 0; i < n; ++i) {if (arr[i] == x) {++x;continue;}if (!s.empty()) {if (s.back() == arr[i]) {s.pop_back();continue;} else if (s.back() > arr[i]) {return false;}}
//        if (x > arr[i]) return false;if (x < n) {s.push_back(x++);--i;} else {return false;}}return true;
}int main() {ios::sync_with_stdio(false);while (cin >> n && n != 0) {arr.resize(n);while (cin >> arr[0] && arr[0] != 0) {s.clear();for (int i = 1; i < n; ++i) cin >> arr[i];if (check()) cout << "Yes\n";else cout << "No\n";}cout << "\n";}
}

感覺這道題的數據很弱，我剛才把s.clear()寫到循環外面去了都AC了。。
添加了一個優化語句：當棧頂元素比結果中的當前元素大時直接不可達，原因是后面的元素肯定都比棧頂元素大。