题解

记录“不快乐”的学生数量 $m$，如果是 $m$ 偶数，那么成对交换，如果 $m$ 是奇数，那么先将前 $m-1$ 个学生成对交换，再把最后一个学生进行一次合理的交换，最终的交换次数为 $\lfloor \frac{m+1}{2} \rfloor$。时间复杂度为 $\mathrm{O} (Tn)$。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1005],cnt;
void solve()//多测函数
{
    cin>>n;
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==i)cnt++;//记录“不快乐”的学生数量
    }
    cout<<(cnt+1)/2<<endl;//输出结果
    return ;
}
signed main()
{
    int T;cin>>T;
    while(T--)solve();
    return 0;
}