欢乐赛#40 | T5题解

T5:

由于座位号是1到n的全排列，我们只需要关注那些座位号与学号相同的学生，记其数量为cnt。
每次交换可同时调整两个学生，因此最优策略是将这些学生成对交换。
最终交换次数最少为(cnt + 1) / 2。

C++代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int a[n];
        int cnt = 0;
        for(int i = 0;i < n;i++){
            cin >> a[i];
            if (a[i] == i + 1){
                cnt++;
            }
        }
        cout << (cnt + 1) / 2 << endl;
    }
    return 0;
}

Python代码：

t = int(input())
for i in range(t):
    n = int(input())
    l = list(map(int,input().split()))
    cnt = 0
    for j in range(n):
        if l[j] == j + 1:
            cnt += 1
    print((cnt + 1) // 2)