自动搬运

查看原文

来自洛谷，原作者为

	破壁人五号 「不过回归空白　空白的原来」| AFO | ICPCer | wallbreaker5th.top

搬运于2025-08-24 22:36:57，当前版本为作者最后更新于2022-03-16 14:01:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这题本人曾经在去年 6 月搬到过联考，而且是在最小化 $m$ 的前提下最小化 $k$ 的加强版。

首先特判所有数已经归位的情况，这时 $m=0$。其余情况下都有 $m=2$（$m=1$ 的话你把 $n+1$ 交换到前 $n$ 个位置之后就回不去了）。

以下的「Solution 1」为本题做法（你可以在 Matrix 67 的博客 里面找到本题），「Solution 2」为最小化 $k$ 的做法。代码是最小化了 $k$ 的。

---

该问题最早出现于 Futurama 第 6 季第 10 集 The Prisoner of Benda。（虽然出题人并没有看过）

下面将交换 $a_i,a_j$ 的操作记为 $(ij)$。记 $x=n+1,y=n+2$。

Solution 1

原动画中给出了如下的构造解：

将排列 $a$ 分解为多个非空的环之积，考虑分别处理每个环。不失一般性地，我们考虑 $a=[2,\cdots n,1]$，对此进行操作：$(1x)\to(2y)\to(3y)\to(4y)\cdots\to(ny)\to(2x)\to(1y)$。在处理完每个环之后，$x,y$ 的位置可能互换，此时我们需要再做 $(xy)$。

设 $a$ 为 $r$ 个非空的环之积，环长之和为 $m$，则其需要 $m+2r+(r \bmod 2)$ 次操作。这在环数大于 $2$ 时不是最优解。期望得分 $64$ 分。

Solution 2

这篇论文 给出了最优构造（如果你想要阅读原论文的话，注意此处的操作是自左向右执行的，而论文中是从右向左执行的）：

考虑将原排列分解为多个非空的环 $C_i$ 之积，每个环形如：

$$\begin{pmatrix} a_1,a_2,a_3,\cdots a_k\\ a_k,a_1,a_2,\cdots a_{k-1} \end{pmatrix} $$

以 $C_1$ 为例，我们定义：

• $$G_1(x)=(a_1x)\to (a_2x)\to \cdots\to (a_kx)$$
• $$F_1(x)=(a_1x)$$

进行操作：

$$\begin{aligned} &F_r(y)\to F_{r-1}(y)\to \cdots\to F_{2}(y)\\ \to & \left[(a_1x)\to G_1(y)\to(a_k x)\right] \\ \to &G_2(x)\to G_3(x)\to \cdots \to G_r(x) \end{aligned}$$

设 $a$ 为 $r$ 个非空的环之积，环长之和为 $m$，则其需要 $m+r+2$ 次操作。

其正确性容易验证。我们下面证明这个解是最优的。

证明

首先我们只保留环中的元素，那些不用换位置的元素我们忽略。

假设 $m+r+2$ 的解不是最优，那么操作数 $t<m+r+2$。通过考虑置换的奇偶性（即逆序对个数的奇偶性）我们可以发现 $t\neq m+r+1$，于是我们有 $t\leq m+r$。

另一方面，对于每个元素，它的初始位置与最终位置不同，一定至少被交换过一次。因此 $t\geq m$。

进一步地，考虑第一个环 $C_1=\begin{pmatrix} a_1,a_2,a_3,\cdots a_k\\ a_k,a_1,a_2,\cdots a_{k-1}\end{pmatrix}$，我们考虑环中最后一次被操作到的元素，它一定是与 $x$ 或 $y$ 交换，且把位于这个元素处的、不属于 $C_1$ 的东西扔出去；在这个交换之前，它一定与 $x,y$ 中的一个交换过一次。其余环类似。于是对于每个环，它至少会带来一次额外的操作，于是我们有 $t\geq m+r$。

综上，$t=m+r$，且不可能出现操作 $(xy)$。

类似地，对于每个环，我们考虑环中第一次被操作到的元素，它同样会被交换了两次。于是对于每个环，它首次操作到的元素和最后一次被操作到的元素是同一个。

总结一下，对于环 $C_1$，它有以下性质：

• 有且仅有唯一一个元素 $a\in C_1$，满足有两次关于 $a$ 的操作；
• 对于其他所有 $C_1$ 中的元素，其操作时间在 $a$ 的这两次操作之间。

其余环也有类似性质。

现在对于每个环 $C_i$，定义 $N_i$ 为对其首次操作与最后一次操作之间（不含）的操作数。

不失一般性地，我们：

• 通过给环编号，可以使得 $N_1\leq N_i,\forall 1<i \leq r$；
• 通过交换 $x,y$，可以使得 $(ay)$ 在 $(ax)$ 之前；
• 通过改变第一个环的起点，可以使得 $a$ 为 $C_1$ 的最后一个元素（$a=a_k$）。

现在考虑 $(a_ky)$ 与 $(a_kx)$ 之间（含）的所有包含 $y$ 的操作，记作 $M$。下面我们用反证法证明 $M$ 一定包含 $C_1$ 以外的元素。

假设 $M$ 中只包含 $C_1$ 中的元素。由于我们需要对于 $i=1,2,\cdots k-1$ 把 $a_{i+1}$ 移到 $a_i$，以下操作必须按照如下顺序执行：

$$(a_ky),(a_{k-1}y),\cdots (a_1y)$$

此时 $a_1$ 到达不了 $a_k$，矛盾。

现在假设 $(hy)\in M,h\notin C_1,h\in C_j$，而 $(a_my)$ 为 $M$ 中紧接在 $(hy)$ 之前的操作。显然我们的操作不能把 $a_m$ 最终送到 $h$，$h$ 应当在 $(a_kx),(a_ky)$ 之间出现两次，于是 $N_j<N_1$，矛盾。证毕。

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+10;
int getint(){ int x;scanf("%d",&x);return x; }
int a[N];
bool vis[N];
vector<int>r[N];int cnt=0;
vector<pair<int,int> >ans;
void swp(int x,int y){
    ans.emplace_back(min(x,y),max(x,y));
    swap(a[x],a[y]);
}

int main(){
    int n=getint();
    for(int i=1;i<=n;i++)a[i]=getint();
    a[n+1]=n+1;a[n+2]=n+2;
    for(int i=1;i<=n;i++){
        if(!vis[i]){
            int u=i;
            while(!vis[u]){
                vis[u]=1;
                r[cnt].push_back(u);
                u=a[u];
            }
            // reverse(r[cnt].begin(),r[cnt].end());
            ++cnt;
        }
    }
    vector<int>cy;
    for(int i=0;i<cnt;i++)if(r[i].size()>1)cy.push_back(i);
    if(cy.empty())return puts("0 0"),0;

    for(int i=cy.size()-1;i;--i)swp(r[cy[i]].back(),n+2);
    swp(r[cy[0]].back(),n+1);
    for(int i:r[cy[0]])swp(i,n+2);
    swp(r[cy[0]].front(),n+1);
    for(int i=1;i<cy.size();i++)for(int j:r[cy[i]])swp(j,n+1);
    swp(n+1,n+2);
    
    printf("%d %d\n",2,(int)ans.size());
    for(auto i:ans)
        printf("%d %d\n",i.first,i.second);
    // for(int i=1;i<=n+2;i++)cerr<<"> "<<a[i];cerr<<endl;
    return 0;
}