Codeforces #644 C.Simple Pairs(思维 双指针)

C.Simple pairs

题目大意：（文末有原题）

给出一个数组，判断能否每两个数间都构成 对，对 要满足：奇偶性相同，或者差1；输出“YES” or “NO”；

思路：

首先数组个数必须是偶数，其次如果奇数和偶数的个数均为偶数，则一定可以，否则，一定是多出来一个奇数或者一个偶数，则从后之前查找，如果有两个数满足 a – b = 1，则输出“YES”，注意要先排序后再查找！

代码：

[code]#include <iostream>#include <algorithm>#include <vector>using namespace std;int main() {int n;cin >> n;while(n--) {int m, c = 0, d = 0, flag = 1;		//c,d分别是奇数、偶数的个数cin >> m;vector<int> e;vector<int> o;for(int i = 0; i < m; i++) {int x; cin >> x;if(x % 2) {e.push_back(x);c++;}else {o.push_back(x);d++;}}sort(e.begin(), e.end());sort(o.begin(), o.end());   //要判断有无只相差1的数，需要有相同的排列顺序if(m % 2) {				//如果是奇数，则一定是NOcout << \"NO\" << endl;}else if(c % 2 == 0 && d % 2 == 0) {cout << \"YES\" << endl;		//如果奇数和偶数的个数都是偶数，即奇数偶数成对出现，则是YES；}else{for(c--, d--; c >= 0 && d >= 0;) {if(e[c] > o[d]) {if(e[c] - o[d] == 1) {cout << \"YES\" << endl;flag--;				//flag是标志符号break;}else {c--;}}else {if(o[d] - e[c] == 1) {cout << \"YES\" << endl;flag--;break;}else {d--;}}}if(flag == 1) cout << \"NO\" << endl;}}return 0;}

题目:

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 a 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.

输入：

The first line contains a single integer t (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 n (2≤n≤50) — length of array aa.

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

输出：

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.

样例：

input：                    output：

7

4

11 14 16 12 ———— YES

2

1 8 ———————— NO 

4

1 1 1 1 ——————- YES

4

1 2 5 6 ——————- YES

2

12 13 ——————— YES

6

1 6 3 10 5 8 ————- YES

6

1 12 3 10 5 8 ———— NO