# 官方题解｜欢乐赛#40

T5

这题可以举几个例子思考下，比如原数组为$1, 2, 3$，就是 $3$ 个人的座位号都和自己的学号一样的话，那么至少需要交换$2$次。如果有偶数个人的座位号都和自己的学号一样，那么只要两个两个交换即可，所以当不合法的数量$cnt$是奇数，答案是$\frac{cnt + 1}{2}$，否则答案是 $\frac{cnt}{2}$。

#include <bits/stdc++.h>
using namespace std;
   
const int N = 200010;
int a[N], n, m, k;
 
void solve(){
    cin >> n;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    int ans = 0;
    for(int i = 1; i <= n; i ++ ){
        ans += a[i] == i;
    }
    cout << (ans + 1) / 2 << endl;
}
 
int main(){
    int tt = 1;
    cin >> tt;
    while(tt -- ){
        solve();
    }
    return 0;
}