B、Split Sort

跳转原题点击此：该题地址

1、题目大意

给定一个长度为n的排列（该排列的数字是包含\(1\sim n\)，每个数必须出现一次）。你可以执行以下操作：
选中一个数x，比x小的数按照原来的顺序放在x的左边，大于等于x的数按照原来的顺序放在x的右边。问你将原始排列组成\(a_i == i，i\subseteq (1\sim n)\)的递增排列，最少需要操作几次。

2、题目解析

我们发现当\(x-1\)在\(x\)的右边时，则需要操作一次将\(x-1\)移动到\(x\)的左边，所以只需要找到该数列中有几个这样的数对，那就是至少需要的操作数。

3、具体代码

#include<bits/stdc++.h>

using namespace std;

const int N = 2e5+10;

int T;
int n;
int f[N];

// 原理：如果 x-1 在 x的右边，那么就需要选中x来将x和x-1调换位置
// 所以找到几个这样的数即可
void solve()
{
	cin >> n;
	vector<int> f(n + 1);
	set<int> se;
	int ans = 0;
	for(int i = 1; i <= n; i++)
	{
		cin >> f[i];
		if(f[i] != 1 && !se.count(f[i] - 1))
			ans++;
		se.insert(f[i]);	// 注意，每次都要插入排列
	}
	cout << ans << endl;
}

int main()
{
	cin >> T;
	while (T--)
	{
		solve();
	}

	return 0;
}