D. Twist the Permutation
inputCopy
3
6
3 2 5 6 1 4
3
3 1 2
8
5 8 1 3 2 6 4 7
outputCopy
0 1 1 2 0 4
0 0 1
0 1 2 0 2 5 6 2
总感觉哪年省赛好像有类似的题，水一波题解
题意给你n个数的数组，问你能否通过循环数组还原到1-n ，这里的循环数组是从1号位到当前位进行循环，求每位需要循环操作多少次才能还原到1-n递增排列（输出总次数最少的一个答案）
思路：
我们可以从最后一项开始往前复位，这样每处理完一项之后就不用管了，步步更新，逆向思维
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+7;
int s[N],bk[N],ans[N];
void work(){
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>s[i];
for(int i=n;i>=1;i--){
int idx=0;
int j;
for(j=1;j<=i;j++) if(s[j]==i) break;
ans[i]=j%i;
idx=ans[i];
//cout<<"idx = "<<idx<<endl;
for(j=1;j<=i;j++) bk[(j-idx+i)%i==0?i:(j-idx+i)%i]=s[j];
for(j=1;j<=i;j++) s[j]=bk[j];
//for(j=1;j<=i;j++) cout<<s[j]<<" ";
}
// puts("");
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
cout<<endl;
}
int main(){
int _;
cin>>_;
while(_--){
work();
}
return 0;
}
