CodeForces 1360C - Similar Pairs

题目来源

CodeForces - 1360C

题干

We call two numbers x and y similar if they have the same parity (the same remainder when divided by 2), or if |x−y|=1. For example, in each of the pairs (2,6), (4,3), (11,7), the numbers are similar to each other, and in the pairs (1,4), (3,12), they are not.

You are given an array aa of n (n is even) positive integers. Check if there is such a partition of the array into pairs that each element of the array belongs to exactly one pair and the numbers in each pair are similar to each other.

For example, for the array a=[11,14,16,12], there is a partition into pairs (11,12) and (14,16). The numbers in the first pair are similar because they differ by one, and in the second pair because they are both even.

Input

The first line contains a single integer tt (1≤t≤1000) — the number of test cases. Then tt test cases follow.

Each test case consists of two lines.

The first line contains an even positive integer nn (2≤n≤50) — length of array aa.

The second line contains nn positive integers a1,a2,…,an (1≤ai≤100).

Output

For each test case print:

• YES if the such a partition exists,
• NO otherwise.

The letters in the words YES and NO can be displayed in any case.

Example

input

7
4
11 14 16 12
2
1 8
4
1 1 1 1
4
1 2 5 6
2
12 13
6
1 6 3 10 5 8
6
1 12 3 10 5 8

output

YES
NO
YES
YES
YES
YES
NO

Note

The first test case was explained in the statement.

In the second test case, the two given numbers are not similar.

In the third test case, any partition is suitable.

题目大意

已知两个数，如果这两个数同奇或同偶，他们互为相似数；如果两数绝对值之差等于1，他们互为相似数。

已知一个长度为偶数的一组数，问是否存在一种划分，能恰好将这个组数划分成多个相似数对。

解题思路

题目给出的这组数有两种情况：

1. 奇数的个数与偶数的个数同为偶数个。
2. 奇数的个数与偶数的个数同为奇数个。

第一种情况下，奇数间能两两组成相似数，偶数间也是如此，所以符合题意。

第二种情况下，奇数间两两组成相似数后必然多出一个，偶数间也是如此，如果这一奇一偶能组成相似数，那么符合题意。一奇一偶能组成相似数必须满足两数绝对值之差等于1，如果能找到一组两数绝对值之差等于1的相似数，那么符合题意；如果找不到，那么这组数不满足题意。

实现

#include <iostream>
#include <algorithm>

using namespace std;

int a[100];

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        bool odd = true, even = true;
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        sort(a, a + n); // 排序是方便找“两数绝对值之差等于1”的相似数
        for (int i = 0; i < n; i++) { // 统计奇数和偶数
            if (a[i] % 2 == 0) {
                even = !even;
            } else {
                odd = !odd;
            }
        }
        if (odd && even)cout << "YES" << endl; // 奇数与偶数都为2的倍数
        else {
            bool flag = false;
            for (int i = 0; i < n - 1; i++) {
                if (abs(a[i] - a[i + 1]) == 1) { // 找“两数绝对值之差等于1”的相似数
                    flag = true; // flag = true 即找到“两数绝对值之差等于1”的相似数
                    break;
                }
            }
            if (flag)cout << "YES" << endl; 
            else cout << "NO" << endl;
        }
    }
    return 0;
}

难度：★★