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

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

题目描述：

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

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

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

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

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

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

输入描述：

第一行包含一个整数$n$，为$Murphy$的$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)$

输出描述：

第一行包含一个整数$cost$,表示将考研计划编号变为升序的最小花费。

第二行包含一个整数$num$,表示你需要进行交换的操作次数。$(0 \leq num \leq6 * n)$

接下来$num$行包含两个整数$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;
}