打卡信奥刷题（3076）用C++实现信奥题 P7015 [CERC2013] Crane

张开发
• 2026/4/16 4:27:37 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

打卡信奥刷题（3076）用C++实现信奥题 P7015 [CERC2013] Crane
P7015 [CERC2013] Crane题目描述有nnn个箱子等着装上船。箱子的编号是a1,a2,⋯ ,ana_1,a_2,\cdots,a_na1​,a2​,⋯,an​。你的工作是通过若干次交换将它们从小到大排列。你每次可以选择一个区间将它的前半部分与后半部分交换两半内部的顺序保持不变。你最多可以交换531441531441531441次。输入格式第一行输入包含数据组数TTT。接下来2×T2\times T2×T行表示TTT组数据。每组数据的第一行为n (1≤n≤10000)n\ (1 \leq n \leq 10000)n(1≤n≤10000)表示箱子的数量。第二行为nnn个正整数$a_1,a_2,\cdots,a_n $ 表示箱子的编号。输出格式对于每组数据首先输出一个数mmm表示交换的次数。 然后输出mmm行按照顺序描述每一次交换。对于每次交换输出要交换的区间中第一个元素和最后一个元素的下标。输入输出样例 #1输入 #12 6 5 4 6 3 2 1 5 1 2 3 4 5输出 #15 1 2 4 5 5 6 4 5 1 6 0C实现#includebits/stdc.husingnamespacestd;intt,n,m,a[10005],b[10005];//b数组存位置ints,l[114514],r[114514];intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cint;while(t--){cinn,m1,s0;for(inti1;in;i)cina[i],b[a[i]]i;while(1){while(b[m]m)m;if(mn)break;while(b[m]!m){//还没归位s,l[s]m(b[m]-m1)%2,r[s]b[m];intw(l[s]r[s])/2;for(intil[s];iw;i){swap(a[i],a[iw-l[s]1]);swap(b[a[i]],b[a[iw-l[s]1]]);}}}couts\n;for(inti1;is;i)coutl[i] r[i]\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容

更多文章