11 冰淇淋配对

题目描述

有 $n$ 盒冰淇淋，第 $i$ 盒有 $a_i$ 个。Kyoko 每次吃两个不同口味的冰淇淋，判断能否吃完所有冰淇淋。

解题思路

核心条件

每次吃两个不同口味，意味着：

1. 总数必须为偶数：否则必然剩下一个
2. 最大盒不能超过总数的一半：否则最大的那个口味会剩余

证明

设总量为 $S = \sum a_i$，最大值为 $M = \max a_i$：

• 若 $S$ 为奇数，显然无法配对完成
• 若 $M > S/2$，则最大的那种口味有剩余（因为其他所有加起来也不够和它配对）

这两个条件是充要条件。

代码实现

n = int(input())
a = [int(x) for x in input().split()]

total = sum(a)

# 条件1：总数必须为偶数
if total % 2 != 0:
    print("NO")
    exit()

max_count = max(a)

# 条件2：最大值不能超过总数的一半
if max_count > total // 2:
    print("NO")
    exit()

print("YES")

复杂度分析

• 时间复杂度：$O(n)$（求和 + 求最大值）
• 空间复杂度：$O(1)$

关键点

1. 偶数检查：总数必须是偶数
2. 最大限制：最大盒数量 $\leq$ 总数的一半
3. 这两个条件是充分必要条件