日常训练2025-1-15

E. Sakurako, Kosuke, and the Permutation

rating：1400

https://codeforces.com/contest/2033/problem/E

思路（贪心）

模拟一下题目逻辑我们发现，所以简单排列都是经过1 2 3 4 5 ... n 这样的排列通过每个数只能跟其他位置的一个数有一次交换，或者不交换变来的，

代码

#include <bits/stdc++.h>

typedef std::pair<long long, long long> pll;
typedef std::pair<int, int> pii;
#define INF 0x3f3f3f3f
#define MOD 998244353
using i64 = long long;
const int N = 1e5+5;

void solve(){
	int n, ans = 0;
	std::cin >> n;

	std::map<int, int> mp;
	std::vector<int> v(n+1);
	
	for (int i = 1; i <= n; i++){
		std::cin >> v[i];
		mp[v[i]] = i;
	}


	for (int i = 1; i <= n; i++){
		if (v[i] == i || v[v[i]] == i) continue;
		ans++;
		int s = v[i];
		int t = mp[i];
		std::swap(v[s], v[t]);
		mp[v[s]] = s;
		mp[v[t]] = t;
	}

	std::cout << ans << '\n';

}

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout<<std::setiosflags(std::ios::fixed)<<std::setprecision(2);
	int t = 1, i;
	std::cin >> t;
	for (i = 0; i < t; i++){
		solve();
	}
	return 0;
}