題意#
題目給定由 1 到 \( n \) 共 \( n \) 個整數構成的排列陣列。
任務是依序收集數字 1 到 \( n \)。
收集規則為：只能從陣列最左側向右掃描。
一回合的掃描中，可以連續收集多個所需的數字，前提是這些數字在陣列中出現的順序必須由左至右。
若下個目標數字出現在陣列的左側（即位置早於上一個收集的數字），則需啟動「下一回合」重新自左向右掃描。
我們需要求出收齊所有數字共需幾回合。
思路#
收集目標是嚴格遞增的序列（1, 2, 3…）。
若數字 \( i+1 \) 位於數字 \( i \) 的「右側」，則在同一回合內可順便收集兩者。
但若數字 \( i+1 \) 出現在數字 \( i \) 的「左側」，代表在往右掃描尋找 \( i \) 的過程中，必然會先「錯過」\( i+1 \)。
此時就必須額外開啟一回合掃描，才能回過頭來收集 \( i+1 \)。
由上述推論可知，不需實際模擬多回合的掃描過程，僅需檢查「每個數字在陣列中的位置」。
只要發生「數值 \( i+1 \) 的索引 < 數值 \( i \) 的索引」，總回合數便增加一次。
實作時，先以陣列 pos 紀錄每個數字出現的位置，將第一回合計入後，依序比較各相鄰數字的位置大小判斷是否需要遞增回合數。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n; cin >> n;
// v 是原本的陣列，pos 用來記錄「每個數字出現在陣列的哪個位置」
vector<int> v(n), pos(n);
for (auto &i : v) {
cin >> i;
// 以 0-based 數字數值當作索引，紀錄其在陣列中的位置
pos[i-1] = &i-v.data();
}
// cnt 記錄總共需要的回合數，最少必定需要 1 回合
int cnt = 1;
// 檢查陣列中數值介於 1 至 n-1 的元素（迴圈變數 i 為 0-based）
for (int i = 0; i+1 < n; i++) {
// 若下一個目標數字 (i+1) 出現位置較早（在左側）
// 代表必須額外開啟新的一回合才能收集
if(pos[i+1] < pos[i]) cnt++;
}
// 輸出總共需要的回合數
cout << cnt << '\n';
}
