CF 1863 B

B. Split Sort

一开始想麻烦了，搞的没思路。

这道题只需要遍历一遍数组并查询当前查询的数小\(1\)的数是否查询过，如果没有查询过就代表该数在这个数的后面，\(Ans\)就需要加一，最后输出就行。

代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;

const int N = 1e5 + 10;
int t;
int n, a[N];
bool v[N];

signed main()
{
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    while(t--)
    {
        cin >> n;
        int ans = 0;
        memset(v, 0, sizeof(bool) * (n + 1));
        v[0] = 1;
        for(int i = 1;i <= n;i++)
        {
            cin >> a[i];
            if(!v[a[i] - 1])
            ans++;
            v[a[i]] = 1;
        }
        cout << ans << endl;
    }
    return 0;
}