打卡信奥刷题（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

输入 #1

2 6 5 4 6 3 2 1 5 1 2 3 4 5

输出 #1

5 1 2 4 5 5 6 4 5 1 6 0

C++实现

#include<bits/stdc++.h>usingnamespacestd;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);cin>>t;while(t--){cin>>n,m=1,s=0;for(inti=1;i<=n;++i)cin>>a[i],b[a[i]]=i;while(1){while(b[m]==m)++m;if(m>n)break;while(b[m]!=m){//还没归位++s,l[s]=m+(b[m]-m+1)%2,r[s]=b[m];intw=(l[s]+r[s])/2;for(inti=l[s];i<=w;++i){swap(a[i],a[i+w-l[s]+1]);swap(b[a[i]],b[a[i+w-l[s]+1]]);}}}cout<<s<<'\n';for(inti=1;i<=s;++i)cout<<l[i]<<' '<<r[i]<<'\n';}return0;}

后续

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