CF1637A Sorting Parts 题解

FFTotoro · 2022-02-14 13:32:09 · 题解

考虑将数列分成前后两段再排序的过程后，实质上只需判断左段的最大值不大于右段的最小值。

其实就是看数组是否已排序，若排序了则说明无法更改，没排序则满足条件，输出 YES 即可。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n; cin>>n;
    vector<int> v(n);
    for(auto &i:v)cin>>i;
    if(is_sorted(v.begin(),v.end()))cout<<"NO\n";
    else cout<<"YES\n";
  }
  return 0;
}