526互联

B. Sort with Step

发布时间 2023-04-30 10:26:00作者: Yaowww

题意：

        给定一个长度为n的数组，任意两个数如果满足i-j的绝对值等于k则可以互相交换，若不能通过此操作实现数组排序，则需要使用次数来强制交换，次数小于等于1输出次数，否则输出-1.

分析：

        最优情况下，找出需要操作的数的数量然后两两交换是次数最少的。

代码:

#include <bits/stdc++.h>

#define fi first
#define se second

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int N=2e5+10;

int a[N];
int b[N];

void solve()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n,k;
        cin>>n>>k;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            b[a[i]]=i;
        }
        int sum=0;
        for(int i=1;i<=n;i++)
        {
            int j=b[i];
            if(abs(j-i)%k==0) continue;
            else
            {
                sum++;
            }
        }
        if(sum==0) cout<<0<<'\n';
        else if(sum<=2) cout<<1<<'\n';
        else cout<<-1<<'\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    solve();
    
    return 0;
}