題目鏈接

題意：給定一個數組p長度為n按照規則對下標滿足2 * abs(i - j) >= n進行交換，最后使數組不遞減。輸出用的交換次數和每次交換的下標。（交換次數不能超過5*n次）

題解：

默認i < j,否則交換
abs(i - j) >= n / 2直接交換
i > n / 2也就是說i - 1 >= n / 2，都和1交換需要3次交換。
i <= n / 2并且j <= n / 2也就是說j + n / 2 <= n
則都可以和n交換，需要交換3次
否則i和n交換后j和1交換之后1和n交換之后 再次i和n、j和i交換需要交換5次

#include <bits/stdc++.h>
using namespace std;#define fi first
#define se second
#define ve vector
#define all(x) (x).begin() + 1, (x).end()
#define rep(i, a, b) for (int i = a; i < b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
using pi = pair<int, int>;#define maxn 300005
int n;
ve<int> a, b;
int otp[maxn * 10][2], cnt = 0;inline int red() {int x;cin >> x;return x;
}void sw(int i, int j) {otp[cnt][0] = i, otp[cnt++][1] = j;swap(a[i], a[j]);swap(b[a[i]], b[a[j]]);
}void cal(int i, int j) {if (i == j) {return;}if (i > j) {swap(i, j);}if (abs(i - j) >= n / 2) {sw(i, j);return;}if (i <= n / 2) {if (j <= n / 2) {sw(i, n), sw(j, n), sw(i, n);} else {sw(j, 1), sw(i, n), sw(1, n), sw(j, 1), sw(i, n);} } else {sw(j, 1), sw(1, i), sw(j, 1);}
} void solve() {n = red();a.resize(n + 1), b.resize(n + 1);rep(i, 1, n + 1) {a[i] = red();b[a[i]] = i;}rep(i, 1, n + 1) {cal(i, b[i]);}cout << cnt << '\n';rep(i, 0, cnt) {cout << otp[i][0] << ' ' << otp[i][1] << '\n'; }}int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);int t = 1;while (t--) {solve();}return 0;
}