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输入 #13 6 1 3 4 6 2 5 5 5 4 3 2 1 10 6 8 5 3 4 7 2 9 1 10输出 #12 3 5 or more说明/提示1≤T≤31\le T\le 31≤T≤31≤n≤151 \le n \le 151≤n≤15。C实现#includebits/stdc.husingnamespacestd;#defineREP(i,l,r)for(inti(l);i(r);i)namespaceMilkcat{typedeflonglongLL;typedefpairLL,LLpii;constintN1e65;intn,chk,a[N];voiddfs(intd,intmxdep){if(chk)return;intct0;REP(i,1,n1)ct(a[i]-a[i-1]!1);ct(ct2)/3;// 相当于 ceil(1.0 * ct / 3)if(dctmxdep)return;if(!ct){chk1;return;}REP(L,1,n)REP(R,L,n){REP(k,1,L-1){rotate(ak,aL,aR1),dfs(d1,mxdep);rotate(ak,akR-L1,aR1);}REP(k,R1,n){rotate(aL,aR1,ak1),dfs(d1,mxdep);rotate(aL,aLk-R,ak1);}}}intmain(){cinn,a[n1]n1;REP(i,1,n)cina[i];REP(i,0,4){chk0,dfs(0,i);if(chk){couti\n;return0;}}cout5 or more\n;return0;}}intmain(){intT1;cinT;while(T--)Milkcat::main();return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容