309987: CF1768D. Lucky Permutation

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Lucky Permutation

题意翻译

### 题目描述 给定整数 $n$ 和一个 $1\sim n$ 的排列 $p$。 你可以对排列 $p$ 进行下列操作任意次: - 选择整数 $i,j(1\leq i<j\leq n)$,然后交换 $p_i,p_j$ 的值。 你需要求出至少需要进行上述操作多少次才能使 $p$ 恰有一个逆序对。 每个测试点包含 $t$ 组数据。 ### 输入格式 第一行输入一个整数 $t(1\leq t\leq10^4)$ 表示数据组数,接下来对于每组数据: 第一行输入一个整数 $n(2\leq n,\sum n\leq2\times10^5)$。 接下来输入一行 $n$ 个整数 $p_1,p_2,\cdots,p_n(1\leq p_i\leq n)$,保证 $p$ 是一个 $1\sim n$ 的排列。 ### 输出格式 对于每组数据: 输出一行一个整数表示使 $p$ 恰有一个逆序对所需的最小操作次数。 可以证明一定存在操作方案使得 $p$ 恰有一个逆序对。

题目描述

You are given a permutation $ ^\dagger $ $ p $ of length $ n $ . In one operation, you can choose two indices $ 1 \le i < j \le n $ and swap $ p_i $ with $ p_j $ . Find the minimum number of operations needed to have exactly one inversion $ ^\ddagger $ in the permutation. $ ^\dagger $ A permutation 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). $ ^\ddagger $ The number of inversions of a permutation $ p $ is the number of pairs of indices $ (i, j) $ such that $ 1 \le i < j \le n $ and $ p_i > p_j $ .

输入输出格式

输入格式


The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 2 \cdot 10^5 $ ). The second line of each test case contains $ n $ integers $ p_1,p_2,\ldots, p_n $ ( $ 1 \le p_i \le n $ ). It is guaranteed that $ p $ is a permutation. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式


For each test case output a single integer — the minimum number of operations needed to have exactly one inversion in the permutation. It can be proven that an answer always exists.

输入输出样例

输入样例 #1

4
2
2 1
2
1 2
4
3 4 1 2
4
2 4 3 1

输出样例 #1

0
1
3
1

说明

In the first test case, the permutation already satisfies the condition. In the second test case, you can perform the operation with $ (i,j)=(1,2) $ , after that the permutation will be $ [2,1] $ which has exactly one inversion. In the third test case, it is not possible to satisfy the condition with less than $ 3 $ operations. However, if we perform $ 3 $ operations with $ (i,j) $ being $ (1,3) $ , $ (2,4) $ , and $ (3,4) $ in that order, the final permutation will be $ [1, 2, 4, 3] $ which has exactly one inversion. In the fourth test case, you can perform the operation with $ (i,j)=(2,4) $ , after that the permutation will be $ [2,1,3,4] $ which has exactly one inversion.

Input

题意翻译

### 题目描述 给定整数 $n$ 和一个 $1\sim n$ 的排列 $p$。 你可以对排列 $p$ 进行下列操作任意次: - 选择整数 $i,j(1\leq i<j\leq n)$,然后交换 $p_i,p_j$ 的值。 你需要求出至少需要进行上述操作多少次才能使 $p$ 恰有一个逆序对。 每个测试点包含 $t$ 组数据。 ### 输入格式 第一行输入一个整数 $t(1\leq t\leq10^4)$ 表示数据组数,接下来对于每组数据: 第一行输入一个整数 $n(2\leq n,\sum n\leq2\times10^5)$。 接下来输入一行 $n$ 个整数 $p_1,p_2,\cdots,p_n(1\leq p_i\leq n)$,保证 $p$ 是一个 $1\sim n$ 的排列。 ### 输出格式 对于每组数据: 输出一行一个整数表示使 $p$ 恰有一个逆序对所需的最小操作次数。 可以证明一定存在操作方案使得 $p$ 恰有一个逆序对。

Output

**题目大意:**

题目给出了一个整数 $ n $ 和一个从 $ 1 $ 到 $ n $ 的排列 $ p $。你可以进行任意次以下操作:

- 选择整数 $ i, j (1 \leq i < j \leq n) $,然后交换 $ p_i, p_j $ 的值。

要求出至少需要进行多少次上述操作才能使得排列 $ p $ 恰好有一个逆序对。每个测试点包含 $ t $ 组数据。

**输入输出数据格式:**

**输入格式:**

第一行输入一个整数 $ t (1 \leq t \leq 10^4) $ 表示数据组数。接下来对于每组数据:

- 第一行输入一个整数 $ n (2 \leq n, \sum n \leq 2 \times 10^5) $。
- 接下来输入一行 $ n $ 个整数 $ p_1, p_2, \cdots, p_n (1 \leq p_i \leq n) $,保证 $ p $ 是一个从 $ 1 $ 到 $ n $ 的排列。

**输出格式:**

对于每组数据:

- 输出一行一个整数,表示使排列 $ p $ 恰有一个逆序对所需的最小操作次数。

可以证明一定存在操作方案使得 $ p $ 恰有一个逆序对。

---

**题目描述(英文):**

You are given a permutation $ p $ of length $ n $.

In one operation, you can choose two indices $ 1 \leq i < j \leq n $ and swap $ p_i $ with $ p_j $.

Find the minimum number of operations needed to have exactly one inversion in the permutation.

**输入输出格式:**

**输入格式:**

The first line contains a single integer $ t (1 \leq t \leq 10^4) $ — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $ n (2 \leq n \leq 2 \times 10^5) $.

The second line of each test case contains $ n $ integers $ p_1, p_2, \ldots, p_n (1 \leq p_i \leq n) $. It is guaranteed that $ p $ is a permutation.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \times 10^5 $.

**输出格式:**

For each test case output a single integer — the minimum number of operations needed to have exactly one inversion in the permutation. It can be proven that an answer always exists.**题目大意:** 题目给出了一个整数 $ n $ 和一个从 $ 1 $ 到 $ n $ 的排列 $ p $。你可以进行任意次以下操作: - 选择整数 $ i, j (1 \leq i < j \leq n) $,然后交换 $ p_i, p_j $ 的值。 要求出至少需要进行多少次上述操作才能使得排列 $ p $ 恰好有一个逆序对。每个测试点包含 $ t $ 组数据。 **输入输出数据格式:** **输入格式:** 第一行输入一个整数 $ t (1 \leq t \leq 10^4) $ 表示数据组数。接下来对于每组数据: - 第一行输入一个整数 $ n (2 \leq n, \sum n \leq 2 \times 10^5) $。 - 接下来输入一行 $ n $ 个整数 $ p_1, p_2, \cdots, p_n (1 \leq p_i \leq n) $,保证 $ p $ 是一个从 $ 1 $ 到 $ n $ 的排列。 **输出格式:** 对于每组数据: - 输出一行一个整数,表示使排列 $ p $ 恰有一个逆序对所需的最小操作次数。 可以证明一定存在操作方案使得 $ p $ 恰有一个逆序对。 --- **题目描述(英文):** You are given a permutation $ p $ of length $ n $. In one operation, you can choose two indices $ 1 \leq i < j \leq n $ and swap $ p_i $ with $ p_j $. Find the minimum number of operations needed to have exactly one inversion in the permutation. **输入输出格式:** **输入格式:** The first line contains a single integer $ t (1 \leq t \leq 10^4) $ — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n (2 \leq n \leq 2 \times 10^5) $. The second line of each test case contains $ n $ integers $ p_1, p_2, \ldots, p_n (1 \leq p_i \leq n) $. It is guaranteed that $ p $ is a permutation. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \times 10^5 $. **输出格式:** For each test case output a single integer — the minimum number of operations needed to have exactly one inversion in the permutation. It can be proven that an answer always exists.

加入题单

上一题 下一题 算法标签: