题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805403651522560
Given any permutation of the numbers {0, 1, 2,…, N−1}, it is easy to sort them in increasing order. But what if Swap(0, *) is the ONLY operation that is allowed to use? For example, to sort {4, 0, 2, 1, 3} we may apply the swap operations in the following way:
|
|
Now you are asked to find the minimum number of swaps need to sort the given permutation of the first N nonnegative integers.
Input Specification:
Each input file contains one test case, which gives a positive N (≤10^5) followed by a permutation sequence of {0, 1, …, N−1}. All the numbers in a line are separated by a space.
Output Specification:
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.
Sample Input:
|
|
Sample Output:
|
|
想法
一眼看过去,应该是一道技巧题,不是常规的数据结构和算法。
每一步,把逆序数降到最低。
好像不止,要把每一个都调整到对应的位置。
唉,那是不是,多少个不在自己位置的,就换多少次对了。
怎么有点连通分量的味道,如果哪几个之间错位了,就需要借助一次0位置进行调整。
如果k个之间错位:
包括0:k-1次;不包括0:k+1次
唉,AC了,果然是trick啊,好好想,细细想,这种题估计就是一个小转弯,工作量并不大
答案
|
|