题意简述

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

题目传送门

思路

也是一道水题。

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

我们可以建立两个 multiset 来分别保存奇数和偶数。根据奇偶性,显然 奇数+偶数=奇数。所以如果 aia_i 是奇数,那么我们只需在奇数多重集中查找 aia_i 。若 aia_i 不为第一个元素,则表示有可以与其和为偶数的逆序对,答案为 No,若为第一个元素,则删除该元素(因为逆序对是统计向后的元素,前面的元素为冗余信息)。如果 aia_i 是偶数,那么我们只需在偶数多重集中查找 aia_i 。若 aia_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;
}