题解：CF2101B Quartet Swapping

· · 题解

首先我们注意到奇数位和偶数位是独立的，将其分开考虑。我们考虑贪心地从前向后要求每一位最小，也就是从小到大枚举 i，将与第 i 位奇偶相同的最小值移动到第 i 位上，然后将其删去。

令 n 为当前剩余的数字数量，最小值在第 j 位上。我们发现如果 j \neq n，直接向前交换即可；但是 j = n 较为麻烦，我们考量这样一个示例

[5, 4, 3, 1, 2]\\ [5, 1, 2, 4, 3]\\ [2, 4, 5, 1, 3]\\

我们发现对于 n - 3 进行一次操作即可，这样可以将 j 从 n 调整到 n - 2。

使用链表维护 \mathcal{O}(1) 交换、删除。一共有 n 次找最大值的操作，共 \mathcal{O}(n) 次交换，时间复杂度 \mathcal{O}(n)。

Code：

#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 2e5 + 10;

int t, n;
int a[maxn], nxt[maxn], pre[maxn], ord1[maxn], ord2[maxn];

int main(){
    scanf("%d", &t), a[0] = 1e9;
    while (t--){
        scanf("%d", &n), nxt[0] = 1, fill(ord1 + 1, ord1 + n + 1, 0), fill(ord2 + 1, ord2 + n + 1, 0);
        for (int i = 1; i <= n; i++){
            scanf("%d", &a[i]), pre[i] = i - 1, nxt[i] = i + 1, (i & 1 ? ord1 : ord2)[a[i]] = i;
        }
        const auto cmp = [](int x, int y){return a[x] < a[y];};
        sort(ord1 + 1, ord1 + n + 1, cmp), sort(ord2 + 1, ord2 + n + 1, cmp);
        for (int i = 1, p1 = 1, p2 = 1; i <= n - 3; i++){
            int* ord = i & 1 ? ord1 : ord2, &p = i & 1 ? p1 : p2;
            if (nxt[ord[p]] > n){
                const int q1 = pre[ord[p]], q2 = pre[q1], q3 = pre[q2], q4 = pre[q3];
                nxt[ord[p]] = q3, nxt[q2] = n + 1, nxt[q4] = q1, pre[q1] = q4, pre[q3] = ord[p];
            }
            const int q = nxt[ord[p]];
            nxt[pre[ord[p]]] = nxt[q], pre[nxt[q]] = pre[ord[p]], nxt[q] = nxt[0], pre[nxt[0]] = q, nxt[0] = ord[p], pre[ord[p]] = 0;
            printf("%d ", a[nxt[0]]), pre[nxt[nxt[0]]] = 0, nxt[0] = nxt[nxt[0]], p++;
        }
        for (int i = nxt[0]; i <= n; i = nxt[i]){
            printf("%d ", a[i]);
        }
        putchar('\n');
    }

return 0;
}