wing是什么_强制排序

wing是什么_强制排序给定 n 本书,编号为 1∼n。在初始状态下,书是任意排列的。在每一次操作中,可以抽取其中连续的一段,再把这段插入到其他某个位置。我们的目标状态是把书按照 1∼n 的顺序依次排列。求最少需要多少次操作。输入格式第一行包含整数 T,表示共有 T 组测试数据。每组数据包含两行,第一行为整数 n,表示书的数量。第二行为 n 个整数,表示 1∼n 的一种任意排列。同行数之间用空格隔开。输出格式每组数据输出一个最少操作次数。如果最少操作次数大于或等于 5 次,则输出 5 or more。每个

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

给定 n 本书,编号为 1∼n。

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

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

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

求最少需要多少次操作。

输入格式
第一行包含整数 T,表示共有 T 组测试数据。

每组数据包含两行,第一行为整数 n,表示书的数量。

第二行为 n 个整数,表示 1∼n 的一种任意排列。

同行数之间用空格隔开。

输出格式
每组数据输出一个最少操作次数。

如果最少操作次数大于或等于 5 次,则输出 5 or more。

每个结果占一行。

数据范围
1≤n≤15

输入样例:
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*,每一次变动都会改变3个数的后继,所以我们可以先统计每个数的后继,然后看看当前状态是否能达到要求。

  1. IDA*
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1e2;
string t;
int f(){ 
   
    int tot = 0;
    for(int i = 1;i < n;i ++)
        if(t[i - 1] != t[i] - 1)tot ++;
    return (tot + 2) / 3;
}
bool IDAstar(int u,int maxn){ 
   
    if(f() > maxn - u)return false;
    if(u == maxn){ 
   
        return true;
    }
    string temp = t;
    for(int len = 1;len <= n - 1;len ++){ 
   
        for(int l = 0;l <= n - len;l ++){ 
   
            int r = l + len - 1;
            string substr = temp.substr(l,r - l + 1);
            for(int k = r + 1;k < n;k ++){ 
   
                t.insert(k + 1,substr);
                t.erase(l,r - l + 1);
                if(IDAstar(u + 1,maxn))return true;
                t = temp;
            }
        }
    }
    return false;
}
int a[N];
int main(){ 
   
    int T;
    cin>>T;
    while(T --){ 
   
        cin>>n;
        t = "";
        for(int i = 0;i < n;i ++){ 
   
            cin>>a[i];
        
            t += a[i];
        }
        int maxn = 0;
        while(maxn <= 4 && IDAstar(0,maxn) == false ){ 
   
            maxn ++;
        }
        if(maxn == 5){ 
   
            cout<<"5 or more"<<endl;
        }
        else cout<<maxn<<endl;
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/168841.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 如何正确的理解RPN网络的train和test[通俗易懂]

    如何正确的理解RPN网络的train和test[通俗易懂]刚开始学FasterRCNN时,遇到这么一个困惑不知其他人有没有:RPN网络在程序中的训练是如何进行的?它都训练了网络中的哪些部分?其实这些我们如果不看源码都很难真正理解!我们以Faster-RCNN_TF的源码为例,以下代码取自./lib/networks/VGGnet_train.py#=========RPN============#以下代码的先后顺序我调整了一下,便…

    2022年6月23日
    26
  • idea里面怎么查看自己的激活码(注册激活)2022.03.11

    (idea里面怎么查看自己的激活码)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

    2022年3月13日
    436
  • 最新DataGrip2021.4.x破解版激活码_通用破解码

    最新DataGrip2021.4.x破解版激活码_通用破解码,https://javaforall.net/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

    2022年3月17日
    109
  • 微信公众平台 获取用户openid

    微信公众平台 获取用户openid今天做微信公众号获取用户的openid,圆满成功,特此来一发。 第一步:理解逻辑。 1:获取openid的逻辑获得微信的openid,需要先访问微信提供的一个网址:这个网址名为url1,下面有赋值。通过这个网址,微信用来识别appid信息,在这个网址中,有一个属性redirect_uri,是微识别完appid后,进行跳转的操作,可以是网页,也可以是servlet,我这里用的是…

    2022年6月26日
    87
  • jmeter常见面试题_hr面试问题大全及答案

    jmeter常见面试题_hr面试问题大全及答案问题列表在项目中如何用jmeter进行http接口测试?Jmeter常用元件有哪些?jmeter如何管理cookie和session信息?jmeter中如何实现关联?jmeter中断言方式?jmeter参数化的方式有哪几种可以实现?Jmeter怎么录制,怎么过滤?JMeter结果树响应数据中文乱码如何解决?用户定义的变量和用户参数的区别?Jmeter怎么实现持续集成测试?在项目中如何用jmeter进行http接口测试?(重点)在Jmeter安装目录bin中,找到jmet

    2022年9月30日
    2
  • urlopen error errno111(英雄联盟报错error)

    原因获取地址信息失败,通常是由于自动选择的DNS服务器不行解决方法更换DNS服务器控制面板(win+R+control)->网络和Internet2.打开网络共享中心3.打开当前连接的网络,以wifi为例4.打开属性5.打开Internet协议版本46.选择使用特定DNS服务器地址,并设置为114.114.114.1148.设置完成后,错误解决…

    2022年4月18日
    59

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号