Swap Round Sorting

题目描述

给定一个包含排列 1,2,$\dots$,n 的数组，你的任务是使用交换轮次对数组进行排序。在每个交换轮次中，你可以选择任意数量的不相同的元素对并交换每一对。\n你的任务是找到最少的轮次并展示在每一轮中如何选择这些对。

输入格式

第一行输入有一个整数 n：数组的大小。\n第二行有 n 个整数 x_1,x_2,$\dots$,x_n：初始的排列。

输出格式

首先输出一个整数 k：最少的轮次数。\n然后，对于每一轮，输出交换次数以及每个交换的下标。你可以输出任意一个有效解。

5
5 2 1 3 4

2
2
1 3
4 5
1
3 5

提示

$1 \le n \le 2 \cdot 10^5$ 样例解释：初始数组为 [5,2,1,3,4]。在第 1 轮之后，数组变为 [1,2,5,4,3]。在第 2 轮之后，数组变为 [1,2,3,4,5]。

标签: CSES1698|附加题2

来源

CSES1698|附加题2