BISHI44　灵异背包？¶

简单通过率 45.33%python3样例通过牛客 AC贪心

牛客原题　源码

讲解章节：贪心、背包问题

一句话

选出若干数，和为偶数且最大。

解题思路¶

这题考什么¶

奇偶性 + 贪心，跟背包毫无关系（题目名是幌子）。

先把所有数都装进去，得到总和 S（这显然是和的上界）；
若 S 是偶数，直接输出 S；
若 S 是奇数，说明奇数元素的个数是奇数（>= 1），必须扔掉奇数个「奇数」才能把和变偶。扔得越少越好，于是只扔一个，且扔最小的那个奇数，答案 = S - min_odd。

扔偶数元素改变不了奇偶性，只会让和变小，所以不考虑。

数据规模与复杂度¶

n <= 1e5，a_i <= 2e4。O(n) 一遍求和顺带记录最小奇数，不需要排序，也不需要 O(n·S) 的 DP。真按背包写的话状态数是 n * Σa = 1e5 * 2e9，量级上根本不成立 —— 题面里的「背包」二字只是包装，识破奇偶性才是这题的全部。

样例复核¶

样例 1：a = [2,5,6]，S = 13 为奇数，唯一的奇数是 5，答案 13-5 = 8 ✓。样例 2：a = [3]，S = 3 为奇数，扔掉 3 得 0，即「一个也不选」✓。

坑在哪¶

S 为奇数时一定存在奇数元素（奇数个奇数相加才会是奇数），所以 min_odd 一定存在，不会出现「找不到」的分支；
允许一个都不选，和为 0（样例 2：n=1, a=[3]，S=3 奇，扔掉唯一的 3 得 0）；
0 也是偶数，题目保证 a_i >= 1 所以不涉及，但答案可以是 0；
扔的必须是最小的奇数，不是最小的元素。若数组是 [2, 7]，S=9 为奇，扔掉最小元素 2 得 7 仍是奇数，扔 7 才得到正确答案 2。

贪心的一般套路见 47-贪心。

参考实现¶

solutions/BISHI44.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = [int(v) for v in data[1:n + 1]]
    s = sum(a)                      # 全选的和，也是答案的上界
    if s % 2 == 0:
        print(s)                    # 已经是偶数，上界可达，无需舍弃任何数
    else:
        # 总和为奇数 -> 至少有一个奇数，扔掉最小的那个即可
        # v % 2 为 1 时为真，等价于筛出全部奇数元素
        print(s - min(v for v in a if v % 2))


main()

BISHI44 灵异背包？¶