相似

题目

现在规定，若两个数 x 和 y 具有相同的奇偶性，或者 |x-y|=1，则称它们相似。
给定一个由 n 个正整数构成的数组（n 是偶数）。
检查数组是否有这样的成对划分，即数组的每个元素恰好属于一对，并且每对中的数字彼此相似。

解题思路

如果 n 个数中奇数的个数为偶数，则可以根据奇偶性划分对。
否则，需要查找是否有存在两个整数满足 |x-y|=1，若存在，则这两个数属于一对，其他根据奇偶性划分对。
如果上面两个条件均不符合，则不能成对划分。

C++代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int t, n;
    cin >> t;
    while(t--){
        cin >> n;
        vector<int> a(n);
        int cnt = 0;
        for(int i=0; i<n; ++i){
            cin >> a[i];
            if(a[i]%2)
                ++cnt;
        }
        bool flag = false;
        if(cnt%2==0)
            flag = true;
        else{
            sort(a.begin(), a.end());
            for(int i=1; i<n; ++i){
                if(a[i]-a[i-1]==1){
                    flag = true;
                    break;
                }
            }
        }
        if(flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}