CF 1823B B. Sort with Step-Toy模板网

这篇具有很好参考价值的文章主要介绍了CF 1823B B. Sort with Step。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

CF 1823B B. Sort with Step

Problem - B - Codeforces

题意：

给n长的数组，里边只有1-n的数字，问你能不能在k步长的交换内换成升序的1-n

AC代码：

首先给你1-n的数字还要排成增序；

对于3 4 1 2

3在第1个数， abs(3 - 1) % 2 == 0；

所以3可以在步长为2的交换中换回位置3

对于步长为2 ，如果你在1的位置，所有你能换的就是1 3 5 7 …

所以对于a[i],要想能够换到i的位置，就看abs(a[i] - i) % k == 0是否成立

先跑一遍看看有几个位置是换不到的，如果这些位置的数量超过2，那肯定是不可能提前交换一次能处理的了，直接输出-1；

如果刚好有两个位置，那就判断交换之后他们能不能让自己跑回原来的位置：

行的话输出1，不行就-1，

如果只有一个位置换不了，那寄，输出-1；

不存在需要交换的位置，赢，输出0；文章来源地址https://www.toymoban.com/news/detail-428300.html

#include<bits/stdc++.h>
#define IO std::ios::sync_with_stdio(false); \
std::cin.tie(0);                             \
std::cout.tie(0)

#define all(v) v.begin(),v.end()

#define int long long
#define PII pair<ll,int>
#define ld long double
#define x first
#define y second
#define endl '\n'
#define inf 0x3f3f3f3f
using namespace std;
const int N = 2e5+10;
void solve()
{
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1),p(n+1),s;
    bool ok = 1;

    for(int i = 1;i<=n;i++){
        cin>>a[i];
        p[a[i]] = i;
        if(abs(i -  a[i]) % k != 0){
            ok = 0;
            s.push_back(a[i]);
        }
    }
    if(ok)cout<<"0"<<endl;
    else{
        if(s.size() > 2){
            cout<<"-1"<<endl;
        } else{
            if(s.size() == 2){
                auto x = s[0],y = s[1];
                if(abs(p[y] - x) % k == 0 && abs(p[x] - y) % k == 0)cout<<"1"<<endl;
                else cout<<"-1"<<endl;
            } else{
                cout<<"-1"<<endl;
            }
        }
    }
}
signed main(){
    int t;
    cin>>t;
    while(t--)
    {
    solve();
    }
}

到了这里，关于CF 1823B B. Sort with Step的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！