打卡信奥刷题（3458）用C++实现信奥题 P10488 [BAPC 2006 资格赛] Booksort

P10488 [BAPC 2006 资格赛] Booksort

题目描述

给定nnn本书，编号为1∼n1 \sim n1∼n。

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

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

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

求最少需要多少次操作。

输入格式

第一行包含整数TTT，表示共有TTT组测试数据。

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

第二行为nnn个整数，表示1∼n1 \sim n1∼n的一种任意排列。

同行数之间用空格隔开。

输出格式

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

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

每个结果占一行。

输入输出样例 #1

输入 #1

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

输出 #1

2 3 5 or more

说明/提示

1≤T≤31\le T\le 31≤T≤3，1≤n≤151 \le n \le 151≤n≤15。

C++实现

#include<bits/stdc++.h>usingnamespacestd;#defineREP(i,l,r)for(inti=(l);i<=(r);++i)namespaceMilkcat{typedeflonglongLL;typedefpair<LL,LL>pii;constintN=1e6+5;intn,chk,a[N];voiddfs(intd,intmxdep){if(chk)return;intct=0;REP(i,1,n+1)ct+=(a[i]-a[i-1]!=1);ct=(ct+2)/3;// 相当于 ceil(1.0 * ct / 3)if(d+ct>mxdep)return;if(!ct){chk=1;return;}REP(L,1,n)REP(R,L,n){REP(k,1,L-1){rotate(a+k,a+L,a+R+1),dfs(d+1,mxdep);rotate(a+k,a+k+R-L+1,a+R+1);}REP(k,R+1,n){rotate(a+L,a+R+1,a+k+1),dfs(d+1,mxdep);rotate(a+L,a+L+k-R,a+k+1);}}}intmain(){cin>>n,a[n+1]=n+1;REP(i,1,n)cin>>a[i];REP(i,0,4){chk=0,dfs(0,i);if(chk){cout<<i<<'\n';return0;}}cout<<"5 or more\n";return0;}}intmain(){intT=1;cin>>T;while(T--)Milkcat::main();return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容