题解：P11934 [CrCPC 2024] 排序

xiazha · 2025-03-18 21:05:53 · 题解

非常厉害的题目，观察到 n\le10，爆搜，但是复杂度是 O(n!n^3) 的，显然超时，想到加剪枝，这里需要挖掘性质：

注意到设一次操作前的数列为 a，操作后为 b，那么若 \sum_{i=1}^{n-1} [a_i+1=a_{i+1}]\ge \sum_{i=1}^{n-1} [b_i+1=b_{i+1}]，那么这次操作是无效的，不继续搜索，这样就能过了，如果你想要更快，那么观察到答案 \le 6，可以进一步节省时间。

注：才发现是最优解

map<long long,int> mp,pm;
long long val()
{
    long long v=0;
    for(int i=1;i<=n;i++) v+=(a[i]-1)*pw[i];
    return v;
}
void dfs(int step)
{
    long long v=val();
    if(mp[v]<=step&&pm[v]) return;
    if(step>=6||step>=minn) return;
    mp[v]=step;pm[v]=1;
    if(v==ans) minn=min(minn,step);
    int ppp=0,ppp1=0;
    for(int p=1;p<n;p++)
        if(a[p]+1==a[p+1])
            ppp++;
    for(int p=1;p<n;p++)
        if(a[p]>a[p+1])
            ppp1++;
    for(int i=0;i<=n;i++)
        for(int j=i;j<=n;j++)
            for(int k=j;k<=n;k++)
            {
                int cnt=0,b[11];
                memcpy(b,a,sizeof(a));
                for(int p=j+1;p<=k;p++) a[++cnt]=b[p];
                for(int p=1;p<=i;p++) a[++cnt]=b[p];
                for(int p=k+1;p<=n;p++) a[++cnt]=b[p];
                for(int p=i+1;p<=j;p++) a[++cnt]=b[p];
                int pp=0,pp1=0;
                for(int p=1;p<n;p++)
                    if(a[p]+1==a[p+1]) pp++;
                for(int p=1;p<n;p++)
                    if(a[p]>a[p+1]) pp1++;
                if(ppp>=pp||pp1>ppp1)
                {
                    memcpy(a,b,sizeof(b));
                    continue;
                }
                dfs(step+1);
                memcpy(a,b,sizeof(b));
            }
}
signed main()
{
    cin>>n;
    pw[0]=1;
    for(int i=1;i<=n;i++) pw[i]=pw[i-1]*10,ans+=(i-1)*pw[i];
    for(int i=1;i<=n;i++) cin>>a[i];
    dfs(0);
    if(minn==1e9) cout<<6;
    else cout<<minn;
    return 0;
}