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

首先，由于 所以记数即可，再加上cnt+1/2这个公式，就可以写出来

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

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