AtCoder Beginner Contest 350

Sort

题目

输入长度为 \(n\) 的数组 \(a\)，表示从 \(1\) 到 \(n\) 的排列。输出操作的次数和过程，使得排列有序。每次操作可以交换 \(a_{i}\) 和 \(a_{j}\)，其中 \(1\leq i<j\leq n\)。

数据范围：\(2\leq n\leq 2\times 10^{5}\)。

思路

如果 \(a_{i}=i\)，则说明 \(a_{i}\) 在正确的位置上。否则，\(a_{i}\) 应该移动到位置 \(a_{i}\) 上，即交换下标 \(i\) 和 \(a_{i}\) 的值。这样每次交换都至少使得一个数在正确的位置上，最多交换 \(n-1\) 次，时间复杂度为 \(O(n)\)。PS：太久没做题，竟然没有做出来。比赛时多此一举，使用的是下标数组 + 排序做的，其实也没问题，就是最后没有按照大小顺序输出。

代码

public static void solve() {
    int n = io.nextInt();
    int[] a = new int[n];
    for (int i = 0; i < n; i++) {
        a[i] = io.nextInt() - 1;
    }

    List<int[]> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        while (a[i] != i) {
            ans.add(new int[]{Math.min(i, a[i]), Math.max(i, a[i])});
            int t = a[a[i]]; a[a[i]] = a[i]; a[i] = t;
        }
    }

    io.println(ans.size());
    for (var t : ans) {
        io.println((t[0] + 1) + " " + (t[1] + 1));
    }
}