题解 | #翻转排序#

K. 翻转排序

知识点：选择排序、排列的性质

重要发现：可以通过翻转 之后再翻转 来交换 , 两个元素的位置，而不影响其他位置。

维护每个位置的元素、以及每个元素在什么位置这两个数组，每次把元素 换到第 个位置上，同时更新这两个数组中的信息。

如果没发现这个性质，也可以使用 Splay 等数据结构维护每个元素的位置，这样只用 次翻转操作就可以了。当然，这种做法有点超纲了，并不推荐这样做。

标程

C++

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 200000 + 9;

int n;
int a[N], pos[N];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        pos[a[i]] = i;
    }

    vector<pair<int, int>> ans;
    for (int i = 1; i <= n; ++i)
    {
        int l = i, r = pos[i];
        swap(pos[a[i]], pos[i]);
        swap(a[l], a[r]);
        ans.push_back({l, r});
        if (r - l >= 2) // 区间长度大于等于 3
            ans.push_back({l + 1, r - 1});
    }

    cout << ans.size() << '\n';
    for (auto [l, r] : ans)
        cout << l << ' ' << r << '\n';
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static Kattio io = new Kattio();

    public static void main(String[] args) {
        int n = io.nextInt();
        int a[] = new int[n + 1];
        int pos[] = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = io.nextInt();
            pos[a[i]] = i;
        }
        Vector<int[]> ans = new Vector<>();
        for (int i = 1; i <= n; i++) {
            int l = i, r = pos[i];

            int tmp = pos[a[i]];
            pos[a[i]] = pos[i];
            pos[i] = tmp;

            tmp = a[l];
            a[l] = a[r];
            a[r] = tmp;

            ans.add(new int[]{l, r});
            if (r - l >= 2) {
                ans.add(new int[]{l + 1, r - 1});
            }
        }
        io.println(ans.size());
        for (int[] p : ans) {
            io.println(p[0] + " " + p[1]);
        }

        io.close();
    }
}

class Kattio extends PrintWriter {
    private BufferedReader r;
    private StringTokenizer st;
    // 标准 IO
    public Kattio() { this(System.in, System.out); }
    public Kattio(InputStream i, OutputStream o) {
        super(o);
        r = new BufferedReader(new InputStreamReader(i));
    }
    // 在没有其他输入时返回 null
    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(r.readLine());
            return st.nextToken();
        } catch (Exception e) {}
        return null;
    }
    public int nextInt() { return Integer.parseInt(next()); }
    public double nextDouble() { return Double.parseDouble(next()); }
    public long nextLong() { return Long.parseLong(next()); }
}

Python

n = int(input())
a = [0] + list(map(int, input().split()))
pos = [0] * (n + 1)
for i in range(1, n + 1):
    pos[a[i]] = i
ans = []
for i in range(1, n + 1):
    l, r = i, pos[i]
    pos[a[i]], pos[i] = pos[i], pos[a[i]]
    a[l], a[r] = a[r], a[l]
    ans.append((l, r))
    if r - l >= 2:
        ans.append((l + 1, r - 1))
print(len(ans))
for l, r in ans:
    print(l, r)