小圓養了一隻可愛的小黑狗，但由於一時想不到什麼特別的名字，因此就叫牠「CuteBlack Dog」，簡稱 CBD。CBD 非常聰明，可以認得阿拉伯數字，也因此得到小圓的鍾愛。
在小圓的細心照料之下，CBD 日漸發福，小圓眼見這樣事情不太妙，於是設計一個遊戲讓 CBD 在玩的時候可以順便運動。
小圓設計的遊戲是這樣的：他先準備了 N 張紙卡，上面依序寫著 1 至 N 的各個正整數，並將這些紙卡在地上亂序的由左到右排成一列。接著他讓 CBD 先由最左邊的紙卡跑到最右邊的紙卡，再從最右邊跑回最左邊，不斷折返，並規定途中只要遇到寫著目前所剩餘的紙卡中，數值最小的那張紙卡，就要將該紙卡叼走，否則不能把該紙卡叼走。
舉例來說，假設一開始共有 5 張卡片，由左而右依序為 1, 4, 2, 5, 3，則 CBD 第一次由左端跑到右端時，延路會叼走 1, 2, 3 三張紙卡，折返往左跑時會叼走 4，又折返往右跑時再把 5 叼走。
小圓想請你幫他算一下，給定一開始的紙卡排列方式，CBD 一共至少需要改變幾次方向才能把所有紙卡都叼走呢？
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 測試資料的輸入共有兩列。 第一列為正整數 N，表示紙卡的數量。 第二列包含 N 個正整數，以空白隔開，表示由左到右紙卡上所寫的數值，保證 1 至 N 都 會恰好出現一次。 | 請輸出一列，其中包含一個整數，為 CBD 折返 (改變方向) 的次數。 |
| 2 1 2 | 0 |
| 5 1 4 2 5 3 | 2 |
| 4 4 3 2 1 | 1 |
| 1 1 | 0 |
解題思路
將資料用 Pair 的方式收起來，第一個欄位是目前位置的數字，第二個欄位是這個數字的位置。將這些資料使用陣列收起來，並且進行排序。排序過後，將陣列從頭跑到尾，並且紀錄目前是往右走還是往左走，如果目前數字的位置是目前位置的反方向，則將答案 +1 且換方向。
範例程式碼－ZeroJudge B684: 狗狗遊戲
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
pair<int, int> num[1000005] = {};
for (int i = 0; i<N; i++) {
int tmp;
cin >> tmp;
num[i] = make_pair(tmp, i);
}
sort(num, num+N);
string sign = "Big";
int position = 0, ans = 0;
for (int i = 0; i<N; i++) {
if (sign == "Big") {
if (num[i].second >= position) position = num[i].second;
else {
ans++;
sign = "Small";
position = num[i].second;
}
}
else {
if (num[i].second < position) position = num[i].second;
else {
ans++;
sign = "Big";
position = num[i].second;
}
}
}
cout << ans << "\n";
}
//ZeroJudge B684
//Dr. SeanXD