Codeforces Round #746 (Div. 2) B. Hemose Shopping

原题链接:Problem - 1592B - CodeforcesCodeforces Round #746 (Div. 2) B. Hemose Shoppinghttps://codeforces.com/problemset/problem/1592/B

 实现目标:对输入的数组A中的(r,l)进行交换排序,l-r>=x

解题思路:发现  如果[n-x,x-1]这段范围不为空集  那么其中的内的数无法与任何数进行交换  而其他位置的数都能受一定限制地*交换。

算法实现:比较排序前后[n-x,x-1]范围内的数值是否相等来判断目标能否实现(毕竟里面的数无法进行交换就总存在一个元素无法交换到本应该对应的位置)

c++代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
int a[N],tmp[N];
int main(){
    int q;cin>>q;
    while(q--){
        int n,x;
        scanf("%d%d",&n,&x);
        for(int i=0 ;i<n ;i++) {                //放入元素
            scanf("%d" ,&a[i]);
            tmp[i]=a[i];
        }
        sort(tmp,tmp+n);
        int f=1 ;
        for( int i = x-1  ;i > n-x-1 ;i --){    //比较区间内的所有元素
            if  (tmp[i] != a[i]) {
               f=0;
               break;
            }
        }
        cout<<(f?"YES\n":"NO\n");        
    }
    return 0;
}

上一篇:68.机器人的运动范围


下一篇:idea spring boot maven打包