310581: CF1855A. Dalton the Teacher
Description
Dalton is the teacher of a class with $n$ students, numbered from $1$ to $n$. The classroom contains $n$ chairs, also numbered from $1$ to $n$. Initially student $i$ is seated on chair $p_i$. It is guaranteed that $p_1,p_2,\dots, p_n$ is a permutation of length $n$.
A student is happy if his/her number is different from the number of his/her chair. In order to make all of his students happy, Dalton can repeatedly perform the following operation: choose two distinct students and swap their chairs. What is the minimum number of moves required to make all the students happy? One can show that, under the constraints of this problem, it is possible to make all the students happy with a finite number of moves.
A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).
InputEach test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.
The first line contains a single integer $n$ ($2 \le n \le 10^5$) — the number of students.
The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — $p_i$ denotes the initial chair of student $i$. It is guaranteed that $p$ is a permutation.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
OutputFor each test case, output the minimum number of moves required.
ExampleInput5 2 2 1 3 1 2 3 5 1 2 5 4 3 4 1 2 4 3 10 10 2 1 3 6 5 4 7 9 8Output
0 2 2 1 1Note
In the first test case, both students are already happy, so Dalton can perform $0$ moves.
In the second test case, Dalton can swap the chairs of students $1$ and $2$ to get the array $[2, 1, 3]$. Then he can swap chairs of students $2$ and $3$ to get the array $[2, 3, 1]$. At this point all the students are happy, and he performed $2$ moves. It is impossible to perform the task with fewer moves.
In the third test case, by swapping the chairs of students $1$ and $2$ and then swapping the chairs of students $4$ and $5$, Dalton gets the array $[2, 1, 5, 3, 4]$ in $2$ moves.
Input
题意翻译
# Dalton the Teacher ## 题目描述： Dalton是一位老师，他有 $n$ 名学生，每名学生的编号为 $1\sim n$ ，教室里有 $n$ 把椅子，椅子的编号也是 $1\sim n$ 。一开始学生 $i$ 坐在凳子 $p_i$ 上，可以保证 $p_i$ 这个数不会出现多次，且 $p_i \le n$ 。 如果一个学生的编号与他（她）的椅子编号不相同，那么学生就会高兴。为了让所有学生都开心，Dalton可以将两个不同的学生交换椅子的编号，文让所有学生开心至少需要多少次交换？可以证明，在这个问题的约束下，用有限的动作让所有学生都感到高兴是可能的。 ## 输入格式 第一行一个 $t$ ( $ 1 \le t \le 1000 $ )，表示测试用例的数量。 对于每个测试用例，第一行一个 $n$ ($2\le n\le 10^5$) 表示学生人数。 第二行一共 $n$ 各种整数 $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $)表示学生 $i$ 的初始椅子编号。 保证所有测试用例的$n$总额不超过$10^5$。 ##输出格式 对于每个测试用例，输出所需的最小移动次数。 ##样例 #1. ###样例输入 #1. ``` 5 2 2 1 3 1 2 3 5 1 2 5 4 3 4 1 2 4 3 10 10 2 1 3 6 5 4 7 9 8 ``` ###样例输出 #1. ``` 0 2 2 1 1 ```Output
Dalton是一个有n个学生的老师，学生编号从1到n。教室里有n张椅子，编号也是从1到n。最初，学生i坐在椅子p_i上。保证p_1, p_2, ..., p_n是一个长度为n的排列。
如果学生的编号和椅子的编号不同，那么这个学生就是快乐的。为了让所有学生都快乐，Dalton可以反复进行以下操作：选择两个不同的学生并交换他们的椅子。求使所有学生都快乐所需的最小移动次数。可以证明，在这个问题的约束下，可以通过有限的移动次数使所有学生都快乐。
输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 1000），表示测试用例的数量。
- 每个测试用例的第一行包含一个整数n（2 ≤ n ≤ 10^5），表示学生的数量。
- 第二行包含n个整数p_1, p_2, ..., p_n（1 ≤ p_i ≤ n），其中p_i表示学生i的初始椅子。保证p是一个排列。
- 保证所有测试用例的n之和不超过10^5。
输出：
- 对于每个测试用例，输出使所有学生都快乐所需的最小移动次数。
示例：
输入：
```
5
2
2 1
3
1 2 3
5
1 2 5 4 3
4
1 2 4 3
10
10 2 1 3 6 5 4 7 9 8
```
输出：
```
0
2
2
1
1
```
注意：
- 在第一个测试用例中，两个学生都已经快乐，所以Dalton可以执行0次移动。
- 在第二个测试用例中，Dalton可以通过交换学生1和学生2的椅子，然后交换学生2和学生3的椅子，使得所有学生都快乐，共进行了2次移动。无法用更少的移动次数完成任务。
- 在第三个测试用例中，通过交换学生1和学生2的椅子，然后交换学生4和学生5的椅子，Dalton在2次移动内得到了排列[2, 1, 5, 3, 4]。题目大意： Dalton是一个有n个学生的老师，学生编号从1到n。教室里有n张椅子，编号也是从1到n。最初，学生i坐在椅子p_i上。保证p_1, p_2, ..., p_n是一个长度为n的排列。 如果学生的编号和椅子的编号不同，那么这个学生就是快乐的。为了让所有学生都快乐，Dalton可以反复进行以下操作：选择两个不同的学生并交换他们的椅子。求使所有学生都快乐所需的最小移动次数。可以证明，在这个问题的约束下，可以通过有限的移动次数使所有学生都快乐。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 1000），表示测试用例的数量。 - 每个测试用例的第一行包含一个整数n（2 ≤ n ≤ 10^5），表示学生的数量。 - 第二行包含n个整数p_1, p_2, ..., p_n（1 ≤ p_i ≤ n），其中p_i表示学生i的初始椅子。保证p是一个排列。 - 保证所有测试用例的n之和不超过10^5。 输出： - 对于每个测试用例，输出使所有学生都快乐所需的最小移动次数。 示例： 输入： ``` 5 2 2 1 3 1 2 3 5 1 2 5 4 3 4 1 2 4 3 10 10 2 1 3 6 5 4 7 9 8 ``` 输出： ``` 0 2 2 1 1 ``` 注意： - 在第一个测试用例中，两个学生都已经快乐，所以Dalton可以执行0次移动。 - 在第二个测试用例中，Dalton可以通过交换学生1和学生2的椅子，然后交换学生2和学生3的椅子，使得所有学生都快乐，共进行了2次移动。无法用更少的移动次数完成任务。 - 在第三个测试用例中，通过交换学生1和学生2的椅子，然后交换学生4和学生5的椅子，Dalton在2次移动内得到了排列[2, 1, 5, 3, 4]。