题目描述

给定n本书，编号为1-n。

在初始状态下，书是任意排列的。

在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。

我们的目标状态是把书按照1-n的顺序依次排列。

求最少需要多少次操作。

样例

输入样例：
3
6
1 3 4 6 2 5
5
5 4 3 2 1
10
6 8 5 3 4 7 2 9 1 10
输出样例：
2
3
5 or more

算法

IDA*()

对于本题

重要思路

1.若第i本书籍的编号+1为第i+1的书籍的编号，则我们将其命名为正确后继，否则其为错误后继
2.对于一个数列，当其错误后继为0时，该数列已经排好，问题解决。
3.我们每一次移动最多可以改变3个位置的后继，这三个后继在最优情况下是都被改为正确的。

    eg：
    3   2  1   4；
    该数列有3个错误后继，移动2到1后，3，1，4的后继被改变。

4.则估价函数可以表示为ceil(tot/3),tot为该序列中错误后继个数

C++ 代码

#include<iostream>
#include<cstdio>
#include<math.h>

using namespace std;

int T,n,a[500],flag=1,ti=1;

void move(int x,int y,int z)
{
    int temp[233],cnt = 0;
    for(int i=y+1;i<=z;i++)temp[++cnt]=a[i];
    for(int i=x;i<=y;i++)temp[++cnt]=a[i];
    cnt=0;
    for(int i=x;i<=z;i++)a[i]=temp[++cnt];
}

int check(){
    int tot=0;
    for(int i=1;i<n;i++)
        if(a[i]+1!=a[i+1])tot++;
    if(a[n]!=n)tot++;
    return tot;
}

bool dfs(int id)
{
    if(id>ti)return false;
    for(int i=1;i<n;i++)
        for(int j=i;j<n;j++)
            for(int k=j+1;k<=n;k++)
            {
                move(i,j,k);
                if(check()==0)return true;
                if((ti-id)*3>=check())
                    if(dfs(id+1)==true)return true;
                move(i,i-j+k-1,k);
            }
    return false;
}

int main(){
    cin>>T;
    while(T--)
    {
        ti=1;
        cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        if(check()==0){cout<<"0"<<endl;continue;}
        while(ti<=4)
        {
            if(dfs(1)==true){cout<<ti<<endl;break;}
            ti++;
        }
        if(ti>4)cout<<"5 or more"<<endl;
    }
    return 0;
}