codeforce #776 div3 1650D - Twist the Permutation

题目链接

思路

由于每次都是每次都是将第i个位置放到第一个位置上其余的元素向后移动i+1到n元素位置不变 操作次数按照1~n所以可倒叙还原 从i=n开始计算到i=1 每次从第一个个位置开始向前找到值为i的元素记录这个元素距离第一个位置的距离(这个距离就代表第i个元素操作了几次) 所以需要将 1到i 上的元素整体连接到到 i+1到n 后面去,顺便把第i个元素的操作次数用数组记录一下

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e4+10;
int a[N];
int b[N];
int cnt[N];
void solve(int n)
{
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);for(int i=n;i>=1;i--){
    if(i!=a[i])    //第i个元素在位置i上就不用操作{
    int idx=1;while(a[idx]!=i)idx++;    //从首位开始遍历找到第i个元素的位置for(int j=1;j<=i;j++)b[(j+i-idx)%i]=a[j];  //用b数组存下改变过后的位置cnt[i]=idx;for(int j=1;j<=i;j++)a[j]=b[j];  //由于i+1到n位置不变所以只需要把1~i的元素改变}}for(int i=1;i<=n;i++)printf("%d ",cnt[i]);cout<<endl;
}
int main()
{
    int T;cin>>T;while(T--){
    int n;cin>>n;solve(n);memset(cnt,0,sizeof cnt);}
}