题目 | Swap!Swap!Swap!Swap!Swap!

“菜鸟杯”华中师范大学程序设计新生赛

E - Swap!Swap!Swap!Swap!Swap!

https://ac.nowcoder.com/acm/contest/26134/E

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述：

作为一个即将开始考研的废物点心, $M u r p h y$ 在退役之后已经着手准备了！

为了考上梦想的枝江大学, $M u r p h y$ 已经制定了未来 $365 * t$ 的考研计划,他在每一张纸上都写下他第几天该做些什么,一共写下了 $n$ 张纸(n是一个偶数),每一张纸都有一个编号 $i$ ,编号表示第 $i$ 天的计划,刚开始所有计划的编号都是升序的。 $M u r p h y$ 觉得只要按照顺序完成写下的计划,就能成为一名 $M a s t e r$ 。

可是嗷子总想带着 $M u r p h y$ 找准进厂时机,于是嗷子将 $M u r p h y$ 的计划全部打乱,并且对 $M u r p h y$ 说: $M i u$ 子啊,我们一起进厂吧。 $M u r p h y$ 不想理会嗷子,只想快点整理好自己的考研计划开始预习...

嗷子看到 $M u r p h y$ 心中如此坚定,于是便开始拷打他,如果 $M u r p h y$ 能够满足嗷子的条件, $M u r p h y$ 便可以继续考研。

$M u r p h y$ 每次可以将两张考研计划进行交换,倘若每次交换的考研计划在当前计划序列中的位置(注意是计划的当前位置,不是计划的编号),满足 $| i - j | \geq n / 2$ ,则 $M u r p h y$ 可以不付出任何代价;否则 $M u r p h y$ 需要付出1的代价。

嗷子需要 $M u r p h y$ 用最小的代价让他自己的考研计划的编号序列,恢复成为初始的样子,即恢复成升序。

输入描述：

第一行包含一个整数 $n$ ，为 $M u r p h y$ 的 $n$ 张考研计划。 $(1 \leq n \leq 5 * 10^{5} 且满足 n 为偶数)$
第二行包含 $n$ 个数, $a_{1}, a_{2}, . . ., a_{n}$ 表示打乱后计划编号序列。 $a_{i}$ 为打乱后在位置 $i$ 的考研计划的编号, $(1 \leq a_{i} \leq n, \forall i, j, a_{i} \neq a_{j})$

输出描述：

第一行包含一个整数 $c o s t$ ,表示将考研计划编号变为升序的最小花费。
第二行包含一个整数 $n u m$ ,表示你需要进行交换的操作次数。 $(0 \leq n u m \leq 6 * n)$
接下来 $n u m$ 行包含两个整数 $l, r$ ,表示交换位置为 $l, r$ 的两个计划,即交换 $a [l] 和 a [r]$ 。 $(1 \leq l, r \leq n)$

示例1：

输入

6
5 6 4 2 1 3

输出

0
10
1 5
2 6
1 4
1 6
2 6
1 4
3 6
6 1
4 1
6 1

说明

Hint：注意输入输出对时限的影响,建议用scanf和printf输入输出
对于样例1
第5天的计划在位置1,第6天的计划在位置2...第3天的计划在位置6。
交换位置为1和5的计划,计划序列变为1 6 4 2 5 3
交换位置为2和6的计划,计划序列变为1 3 4 2 5 6
交换位置为1和4的计划,计划序列变为2 3 4 1 5 6
交换位置为1和6的计划,计划序列变为6 3 4 1 5 2
交换位置为2和6的计划,计划序列变为6 2 4 1 5 3
交换位置为1和4的计划,计划序列变为1 2 4 6 5 3
...
此样例每一次交换都不需要符出代价。

我的笔记：

分析

比赛时没想到代价肯定最低为零，于是开始胡思乱想，然后就放弃了。现在看来，既然它没限制最高多少步完成，那么肯定有个办法能让代价为零。

排序方法

我们首先忽略这个代价限制，只想排序方法。排序方法就是记录各个数字所在的位置，如果这位的数字不对，就把这个地方应有的数字替换过来，从数组第一位开始一直排序到最后一位，可以保证数组能够排好序。

比如6 2 3 4 5 1，从第一位开始排序，第一位应该1，第一位现在的数字不对，我们需要的1在第六位，于是将第六位与第一位交换。以此类推，这个数组就排好序了。

绕开限制方法

然后就得考虑代价限制，我们数组排序的方法不变，只不过有时候不能这么直接，而是得曲线救国一下。首先判断能否直接换，如果可以就直接换，最简单。如果判断下来不能直接换，那么就得借助首尾元素来绕开限制，可以发现有三种情况。（下面是一种例子）

1 2 4 3 5 6
1 3 2 4 5 6
1 2 3 5 4 6

第一种情况，需要换的俩，一个在 $n / 2$ 左边，一个在 $n / 2$ 右边，此时我们可以先将一、四；三、六号位交换，这样就把需要换的两个数据扔到了数组最边上，然后在交换这两个数据，然后再还原一、四；三、六号位。这样一通操作等价于直接交换三、四号位，但绕开了限制。（对应代码if的第三个情况）

第二种情况，需要换的俩都在 $n / 2$ 左边，我们直接把三、六；二、六交换，然后还原三、六，这样等价于二、三交换。（对应代码if的第一个情况）

第三种情况，需要换的俩都在 $n / 2$ 右边，思路同上。（对应代码if的第二个情况）

输出方法

这题目还要在最开始输出操作步数，那就肯定不能变执行边输出，而是得换完后统计好一起输出。我看其他题解，有把每一步组成pair对，然后存到vector里面的，我就直接简单粗暴了，搞个stringstream存下来我的输出，最后再输出就行了。

源码

#include <bits/stdc++.h>

using namespace std;

int sche[500010], pos[500010];
stringstream ans;
int num = 0;

void myswap(int a, int b)
{
    swap(sche[a], sche[b]);
    swap(pos[sche[a]], pos[sche[b]]);
    ans << a << ' ' << b << endl;
    num++;
}

int main(void)
{
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> sche[i];
        pos[sche[i]] = i;
    }

    for (int i = 1; i <= n; i++)
    {
        if (pos[i] == i)
            continue;
        if (abs(pos[i] - i) >= n / 2)
        {
            myswap(i, pos[i]);
        }
        else
        {
            int big = max(i, pos[i]), small = min(i, pos[i]);
            if (big <= n / 2)
            {
                myswap(big, n);
                myswap(small, n);
                myswap(big, n);
            }
            else if (small > n / 2)
            {
                myswap(1, small);
                myswap(1, big);
                myswap(1, small);
            }
            else
            {
                myswap(small, n);
                myswap(1, big);
                myswap(1, n);
                myswap(small, n);
                myswap(1, big);
            }
        }
    }
    cout << "0\n"
         << num << endl;
    cout << ans.str();
    return 0;
}