题解：P12997 [GCJ 2022 #3] Revenge of GoroSort

· · 题解

简要题意

给出一个长度为 N=100 的排列，每次操作将所有数分组，随机打乱每组中数的位置，要求操作次数尽可能少的前提下将其变得有序（从小到大），T=1000 组数据，最大总次数 K=11500。

思路及实现

一个显而易见的做法就是对排列进行循环分解，将同一个循环里的数分为一组。举个例子，排列 1,6,2,4,3,5 的循环分别是 1,6\to5\to3\to2,4，于是我们就可以将 2,3,5,6 分为一组，其他两个数各为一组。

那将一个完全错排的排列随机打乱后期望的固定值是多少？这个问题相当于求一个完全随机的排列期望的固定值。先给结论，无论排列长度多少，期望总是 1。以下是证明过程。

:::info[证明]

设 X 为固定点的数目，X_i 表示是否是固定点，则

X=\sum_{i=1}^nX_i

根据期望的线性性：

E[X]=\sum_{i=1}^nE[X_i]

对于每个 X_i，随机排列中第 i 位元素恰好是 i 的概率均为 \frac{1}{n}。于是代入得到

E[X]=\frac{1}{n}\times n=1

:::

于是你就可以高高兴兴写一发代码交上去。

:::info[Code]

#include<bits/stdc++.h>
using namespace std;
int T,n,k;
int a[1051],c[1051];
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
    cin>>T>>n>>k;
    while(T--)
    {
        while(true)
        {
            for(int i=1;i<=n;i++)
                cin>>a[i];
            int idx=0;
            for(int i=1;i<=n;i++)
                c[i]=0;
            for(int i=1;i<=n;i++)
                if(!c[i])
                {
                    int x=i;
                    idx++;
                    do
                    {
                        c[x]=idx;
                        x=a[x];
                    }while(x!=i);
                }
            for(int i=1;i<=n;i++)
                cout<<c[i]<<(i==n?"\n":" ");
            cout.flush();
            int k;
            cin>>k;
            if(k==-1) return 0;
            if(k==1) break;
        }
    }
}

:::

然后发现只拿到了 18 分，那问题出在哪了？

很明显上面的代码的期望次数与排列中最长循环的长度有关，如果最长循环长度太长操作次数自然更多。解决方法也很简单，对每一组元素的个数做一个上限即可，取 10 左右应该都没问题，虽然这样每一组重排后期望固定点会略微减少，但整体效率会提升。

下面给出代码实现，其实就多判断了一下每组元素个数。

:::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
int T,n,k;
int a[1051],c[1051];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>T>>n>>k;
    while(T--)
    {
        while(true)
        {
            for(int i=1;i<=n;i++)
                cin>>a[i];
            int idx=0;
            for(int i=1;i<=n;i++)
                c[i]=0;
            for(int i=1;i<=n;i++)
                if(!c[i])
                {
                    int x=i;
                    idx++;
                    int tot=0;
                    do
                    {
                        c[x]=idx;
                        x=a[x];
                        tot++;
                    }while(x!=i&&tot<=10);
                }
            for(int i=1;i<=n;i++)
                cout<<c[i]<<(i==n?"\n":" ");
            cout.flush();
            int k;
            cin>>k;
            if(k==-1) return 0;
            if(k==1) break;
        }
    }
}

:::