删不同的数字

目录

1. 题目描述
   1. 输入描述
   2. 输出描述
   3. 示例
2. 解答

题目描述

小 Q 有 n 个数字，每次小 Q 可以选择任意两个不相同的数字，并同时删去它们。问最后你能否删完。

输入描述

第一行数字 T，表示数据组数

对于每组数据

第一行一个数字 n，表示数字个数（保证 n 是偶数）。接下来一行 n 个数 Ai，表示这些数字。

满足 2 ≤ n ≤ 100000，1 ≤ Ai ≤ n。

输出描述

对于每组数据，输出”YES” / “NO” 表示你是否可以删去所有数字。

示例

输入

1

6

1 2 3 4 5 6

输出

YES

解答

当且仅当一个数字出现次数超过 n / 2 时无法删完。问题转化为看数组中是否有元素出现次数超过一半。

T = int(input())
while T > 0:
    T -= 1
    n = int(input())
    arr = input().split(' ')
    cur = arr[0]
    cnt = 1
    for i in range(1, n):
        if arr[i] == cur:
            cnt += 1
        else:
            cnt -= 1
        if cnt == 0:
            cur = arr[i]
            cnt = 1
    cnt = 0
    for num in arr:
        if num == cur:
            cnt += 1
    if cnt > n // 2:
        print("NO")
    else:
        print("YES")

第二次循环求我们第一次循环得到的数时必要的。因为只有当数组里出现次数最多的数字，出现的次数大于 n / 2 才无法完全删除，而第一个循环得到的数字不一定出现了超过 n / 2 次。

还有一种错误的写法：

T = int(input())
while T > 0:
    T -= 1
    n = int(input())
    arr = input().split(' ')
    cnt = 0
    cur = ''
    for num in arr:
        if cnt == 0:
            cnt = 1
            cur =num
            continue
        if cur == num:
            cnt += 1
        else:
            cnt -= 1
        print(num, cur, cnt)
    if cnt == 0:
        print('YES')
    else:
        print('NO')

这种写法在输入为 1 1 2 2 3 3 的时候给出了 NO，但是实际上没有任何数字出现超过 n / 2 次。