CSES – Collecting Numbers

題目連結

題意

給一個 n 跟 1 ~ n 的 permutation。每次你可以從左往右拿數字，但是你拿到數字必須要是遞增的。問最少可以花幾次就拿完全部的數字。

解題方法

由於是從左往右拿，x-1 一定要在 x 右邊才能在一趟被一起照順序拿。
所以，我們可以用 a[i] 的 index 來判斷需要多少趟才能拿完。
如果 idx[x] < idx[x-1]，代表 x 在 x-1 左邊，一定要分兩趟才能拿完，否則可以在一趟就一起拿。

#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector <int> a(n+1), idx(n+1);
    for(int i = 1;i <= n;i++){
        cin >> a[i];
	idx[a[i]] = i;
    }
    int cnt = 1;
    for(int i = 1;i <= n;i++){
	if(idx[i] <= idx[i-1])
	   cnt++;
    }
    cout << cnt << '\n';
}