cf C. AquaMoon and Strange Sort（思維）

題目連結

題意：

給定一個長度為n的數組，每個數字有一個方向，初始全部朝右，每次可以進行一次操作，可以選擇兩個數字交換他們的位置并且方向改變，求進行若幹次操作，是否能将數組變為升序排列且方向全部朝右。

題目分析：

由方向的改變我們可以得知，每個數字如果想要移動至正确位置， 必須進行偶數次操作，如果是奇數，方向就會相反，由這個性質我們可以想到偶數位置上的數，結果也必須在偶數位，奇數位置上的數，結果也必須在奇數位。

我們記錄每個數字初始所在位置，然後排序進行比對。

代碼：

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef pair<double,double>PDD;
typedef set<int>::iterator SIT;
int dx[]={0,-1,0,1},dy[]={-1,0,1,0};
int gcd(int a,int b) {return b?gcd(b,a%b):a;}
int lcm(int a,int b) {return a/gcd(a,b)*b;}
const double eps=1e-6;
const int INF=0x3f3f3f3f,mod=1e9+7;
const int N=1e5+10;
int a[N],b[N];
int n;
int mp[N][5];
signed main(){
    fast;
    int T;
    cin>>T;
    while(T--){
        memset(mp,0,sizeof(mp));
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            mp[a[i]][i%2]++;
        }
        sort(a+1,a+n+1);
        bool ok=true;
        for(int i=1;i<=n;i++){
            if(i%2){
                if(mp[a[i]][1]==0){
                    ok=false;
                    break;
                }
                mp[a[i]][1]--;
            }
            else{
                if(mp[a[i]][0]==0){
                    ok=false;
                    break;
                }
                mp[a[i]][0]--;
            }
        }
        if(ok) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}