CSES - Swap Round Sorting | Sắp xếp hoán đổi
Xem PDF
Điểm:
1800 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho một mảng chứa hoán vị của các số \(1,2,…, n\) và nhiệm vụ của bạn là sắp xếp mảng bằng cách sử dụng các lượt hoán đổi. Trên mỗi lượt hoán đổi, bạn có thể chọn bất kỳ số cặp phần tử riêng biệt nào và hoán đổi chúng. (mỗi phần tử chỉ được chọn một lần cho mỗi lượt hoán đổi)
Nhiệm vụ của bạn là tìm số lượt tối thiểu và chỉ ra các cặp trong mỗi vòng.
Input
- Dòng đầu tiên chứa số nguyên \(n\): kích thước của mảng.
- Dòng thứ hai chứa \(n\) số nguyên \(x_1, x_2,…, x_n\): hoán vị ban đầu.
Output
- Dòng đầu tiên in ra số nguyên \(k\): số lượt tối thiểu.
- Với mỗi lượt, in số lần hoán đổi và các chỉ số của mỗi lần hoán đổi. Bạn có thể in bất kỳ giải pháp hợp lệ nào.
Constraints
- \(1\leq n \leq 2 ⋅ 10^5\)
Example
Sample input
5
5 2 1 3 4
Sample output
2
2
1 3
4 5
1
3 5
Note
- Giải thích: Dãy ban đầu là \([5,2,1,3,4]\). Sau bước thứ nhất, dãy trở thành \([1,2,5,4,3]\). Sau bước thứ hai, dãy trở thành \([1,2,3,4,5]\).
Bình luận
Cho một mảng chứa hoán vị của các số \(1, 2, ..., n\) và nhiệm vụ của bạn là sắp xếp mảng bằng cách sử dụng các lượt hoán đổi. Trên mỗi lượt hoán đổi, bạn có thể chọn bất kỳ số cặp phần tử riêng biệt nào và hoán đổi chúng. (Mỗi phần tử chỉ được chọn một lần cho mỗi lượt hoán đổi)
Nhiệm vụ của bạn là tìm số lượt tối thiểu và chỉ ra các cặp trong mỗi vòng.
Input
Output
Example
Test 1
Input
Output