Minimum Swaps to Sort
mediumArrays & Prefix Sums+20 XPTime limit 2s
Students with different heights stand in a line. In one move you may swap any two students (not only neighbours). What is the minimum number of swaps to arrange them in increasing order of height?
Input:
- line 1:
n - line 2:
ndistinct integers (the heights, in line order)
Output: the minimum number of swaps.
Constraints: 1 ≤ n ≤ 10⁵, 1 ≤ a[i] ≤ 10⁹, all values distinct.
Think about it: sort a copy to learn where each element must go. Following "element at i belongs at j" splits the positions into cycles. A cycle of length L needs exactly L − 1 swaps, so the answer is n − (number of cycles).
Sample input 1
5 101 758 315 730 472
Sample output 1
2
Sample input 2
4 4 3 2 1
Sample output 2
2
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).