双元素插入排序(Insertion Sort 2) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if (!(cin >> n)) return 0;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i];

    int inv = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (p[i] > p[j]) inv ^= 1;
        }
    }
    if (inv & 1) {
        cout << "No\n";
        return 0;
    }

    vector<pair<int, int>> ops;
    auto apply = [&](int i, int j) {
        ops.push_back({i, j});
        int a = p[i - 1], b = p[i];
        p.erase(p.begin() + (i - 1), p.begin() + (i + 1));
        p.insert(p.begin() + j, {a, b});
    };

    for (int val = 1; val <= n - 2; ++val) {
        int pos = (int)(find(p.begin(), p.end(), val) - p.begin()) + 1;
        if (pos == val) continue;
        if (pos == n) {
            apply(n - 1, val - 1);
            pos = val + 1;
        }
        apply(pos, val - 1);
    }

    cout << "Yes\n" << ops.size() << "\n";
    for (auto [i, j] : ops) {
        cout << i << " " << j << "\n";
    }
    return 0;
}