AT_arc121_c

_luanyi_ · 2024-08-23 14:31:25 · 题解

发现 n 很小，n^2 的操作次数很宽，因此直觉上来讲可以乱搞来做。

在众多排序算法中选择一个，那就选择排序吧。

具体地，从大到小依次给数尝试往右移，以试图让它能移到他最终要在的位置。

设这一次操作的操作编号奇偶性为 c\in\{0,1\}，当前轮到的数下标为 i。

当 i\bmod 2=c 时，显然可以直接移动。重点在 i\bmod 2\neq c 的情况。

在这种情况下，我们尝试浪费这一次操作，若能不太改变局面，那么下一个操作就变成了 i\bmod 2=c 的操作，就可以将当前的数向右移以靠近目标。

怎么浪费呢？一个比较简单的想法是试图操作最左边几个位置，因为这几个位置一定是在右边所有位置都已经归为后才需要去处理的，因此在右边没怎么搞好时我们并不关心最左边那几个位置长什么样。

一个简单的实现流程如下：

• 若 c=1：若 i=2 则操作位置 3，否则操作位置 1。注意到这里在 n=3 的时候只能操作 1，需要特判。
• 若 c=0：发现如果只操作 2 会导致死循环（比如对于 4,3,1,2）。因此可以构造操作序列：操作 2，再操作 1，再操作 2。其他合理的操作方法也是可以的，这里连续三次看似无厘头的操作是为了防止死循环。为什么是先 2 再 1 再 2 呢？实际上是我这么写了之后发现某样例不会死循环了之后交上去直接过了。

然后如果不死循环的话正确性就是对的了。

实践是检验真理的唯一标准，交上去没有死循环，那就过了吧。

const int maxn = 200200;
int n, a[maxn], c;
vector <int> ansl;
void work (int i) {
    c ^= 1; swap (a[i], a[i+1]); ansl.pb (i);
}
void solve () {
    cin >> n;
    fq (i, 1, n) cin >> a[i];
    ansl.clear ();
    c = 1;
    while (1) {
        bool flg = 1;
        for (int i = 1; i < n; i++) if (a[i] > a[i + 1]) {flg = 0; break;}
        if (flg) break;
        int x = n; while (a[x] == x) --x;
        int j = 1; while (a[j] != x) ++j;
        if ((j & 1) == c) {work (j); continue;}
        if (c == 1) {
            if (j == 2) {work (n == 3 ? 1 : 3); continue;}
            work (1);
        } else {
            work (2); work (1); work (2);
        }
    }
    cout << ansl.size () << endl;
    for (auto i : ansl) cout << i << ' '; cout << endl;
}

注意到复杂度大概是 O(n^3) 规模，因此不优化是不会超时的。