CF1148C

FiraCode · 2024-01-09 19:44:30 · 题解

思路：

可以依次从小到大考虑归位。

对于第 i 大，若它原本的位置和它要在的位置满足题目中给出的关系那么直接交换即可。

若它原本的位置和它要在的位置相等直接跳过即可。

否则在这个数的后面或前边一定有一部分中数的个数是 \ge \frac n 2。

• 若这个数的后边数的个数 \ge \frac n 2，那么可以考虑直接跳到 n，然后再跳到它应在的位置。
• 若这个数的前边数的个数 \ge \frac n 2，那么可以考虑先于第一个数交换，然后若于它应在的位置距离满足条件就直接跳，否则就先跳到 n，再跳到应该在的位置，然后再将第一个数换回去。

然后最多的交换次数就是这个数前面的数的个数 \ge \frac n 2 且跳到 1 之后要再跳到 n，再跳回应在的位置，所以最多的交换次数为 4n，低于上界可行。

#include <bits/stdc++.h>

using namespace std;

int n;
int a[300010];
pair<int, int> b[300010];
int di[300010];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        b[i] = {a[i], i};
    }

    sort(b + 1, b + 1 + n);
    for (int i = 1; i <= n; ++i) {
        di[i] = b[i].second;
    }

    vector<pair<int, int>> opt;

    for (int i = 1; i <= n; ++i) {
        // cout << i << ' ' << a[1] << "---\n";
        // printf("QAQWQ\n");
        // for (int j = 1; j <= n; ++j) printf("%d ", a[j]);
        // puts("");
        if (di[i] == i) continue;
        else if (2 * abs(di[i] - i) >= n) {
            opt.push_back({i, di[i]});
            swap(di[a[i]], di[i]);
            swap(a[i], a[di[a[i]]]);
        } else {
            if (n - di[i] >= n / 2) {
                opt.push_back({di[i], n});
                swap(di[i], di[a[n]]);
                swap(a[di[a[n]]], a[n]);
                opt.push_back({i, n});
                swap(di[a[n]], di[a[i]]);
                swap(a[i], a[n]);
            } else {
                opt.push_back({1, di[i]});
                swap(di[a[1]], di[i]);
                swap(a[1], a[di[a[1]]]);
                // cout << a[1] << endl;
                if (i - 1 >= n / 2) {
                    opt.push_back({1, i});
                    swap(di[a[1]], di[a[i]]);
                    swap(a[1], a[di[a[1]]]);
                    opt.push_back({1, di[1]});
                    swap(di[a[1]], di[1]);
                    swap(a[1], a[di[a[1]]]);
                } else {
                    opt.push_back({1, n});
                    swap(di[a[1]], di[a[n]]);
                    swap(a[1], a[n]);
                    // cout << a[1] << "---\n";
                    opt.push_back({i, n});
                    swap(di[a[i]], di[a[n]]);
                    swap(a[i], a[n]);
                    // cout << a[1] << "---\n";
                    opt.push_back({di[1], 1});
                    // cout << di[1] << ' ' << a[1] << ' ' << di[a[1]] << a[di[a[1]]] << endl;
                    swap(di[1], di[a[1]]);
                    swap(a[1], a[di[a[1]]]);
                }
            }
        }
    }

    printf("%d\n", opt.size());
    for (auto v : opt) {
        printf("%d %d\n", v.first, v.second);
    }

    return 0;
}