CF1638B Odd Swap Sort

题意简述

现在有一个序列 $a_1 , a_2,\dots,a_n$ ，你可以交换相邻两个和为奇数的数，问是否能够使序列有序。可以输出 Yes , 不可以输出 No。

思路

也是一道水题。

显然这道题跟逆序对有关。由于交换排序，所以每一对逆序对都一定会被交换。所以只需检查逆序对中是否有和为偶数的就行了。

我们可以建立两个 multiset 来分别保存奇数和偶数。根据奇偶性，显然奇数+偶数=奇数。所以如果 $a_i$ 是奇数，那么我们只需在奇数多重集中查找 $a_i$ 。若 $a_i$ 不为第一个元素，则表示有可以与其和为偶数的逆序对，答案为 No，若为第一个元素，则删除该元素（因为逆序对是统计向后的元素，前面的元素为冗余信息）。如果 $a_i$ 是偶数，那么我们只需在偶数多重集中查找 $a_i$ 。若 $a_i$ 不为第一个元素，则表示有可以与其和为偶数的逆序对，答案为 No，若为第一个元素，则删除该元素（因为逆序对是统计向后的元素，前面的元素为冗余信息）。

参考代码

#include <bits/stdc++.h>
using namespace std;

int T;
int N;
int Num[200010];
multiset< int > odd;
multiset< int > even;

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while(T--) {
        cin >> N;
        odd.clear();
        even.clear();
        for(int i = 1; i <= N; i++) {
            cin >> Num[i];
            if(Num[i] % 2 == 0) {
                even.insert(Num[i]);
            }
            else {
                odd.insert(Num[i]);
            }
        }
        for(int i = 1; i <= N; i++) {
            if(Num[i] % 2 == 0) {
                multiset< int >::iterator it = even.find(Num[i]);
                if(it != even.begin()) {
                    cout << "No" << endl;
                    goto end;
                }
                even.erase(it);
            }
            if(Num[i] % 2 == 1) {
                multiset< int >::iterator it = odd.find(Num[i]);
                if(it != odd.begin()) {
                    cout << "No" << endl;
                    goto end;
                }
                odd.erase(it);
            }
        }
        cout << "Yes" << endl;
        end:
            continue;
    }   
    return 0;
}