题解 | #灵异背包？#

题目链接

灵异背包？

题目描述

给定 $n$ 个正整数，你可以任选其中若干个放入一个“灵异背包”。要求背包内所有数之和为偶数，且在满足此条件的前提下，和要尽可能大。如果一个数也不选，则背包和为 $0$ 。请输出可以获得的最大偶数和。

解题思路

本题要求解一个子集和问题，附加了“和为偶数”和“和最大”两个条件。我们可以采用贪心策略来解决。

核心思想： 为了让和尽可能大，我们最理想的情况是把所有给定的数都选入背包。

计算总和：首先，我们计算出所有 $n$ 个数的总和 total_sum。
分情况讨论：
- 情况一：total_sum 本身就是偶数。 这是最完美的情况。我们已经得到了可能的最大和，并且它满足偶数条件。因此，这个 total_sum 就是最终答案。
- 情况二：total_sum 是奇数。 在这种情况下，我们不能选择全部的数。为了让奇数和变为偶数，我们必须从和中减去一个奇数。为了使最终的和尽可能大，我们应该减去一个最小的数。因此，我们需要从原数组中去掉一个奇数，并且为了保持和最大，我们应该去掉那个值最小的奇数。
  - 在遍历数组计算总和的同时，我们可以记录下遇到的最小的奇数 min_odd。
  - 最终的答案就是 total_sum - min_odd。

特殊情况：

如果 total_sum 是奇数，但数组中不存在任何奇数，这种情况可能吗？不可能。因为只有偶数的和必然是偶数，所以如果总和是奇数，输入中必定至少有一个奇数。
如果唯一的选择是去掉一个奇数后总和变为0（例如，输入只有一个奇数 [3]），那么答案就是0。我们的逻辑 total_sum - min_odd 可以正确处理这种情况（3 - 3 = 0）。

实现要点：

在一次遍历中，可以同时完成求和以及寻找最小奇数两个任务。
由于数字和可能很大，需要使用64位整型（long long 或 long）来存储总和。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    long long total_sum = 0;
    int min_odd = INT_MAX;
    
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        total_sum += num;
        if (num % 2 != 0) {
            min_odd = min(min_odd, num);
        }
    }

    if (total_sum % 2 == 0) {
        cout << total_sum << endl;
    } else {
        if (min_odd == INT_MAX) { // 理论上不会发生
            cout << 0 << endl;
        } else {
            cout << total_sum - min_odd << endl;
        }
    }

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        long totalSum = 0;
        int minOdd = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            int num = sc.nextInt();
            totalSum += num;
            if (num % 2 != 0) {
                minOdd = Math.min(minOdd, num);
            }
        }

        if (totalSum % 2 == 0) {
            System.out.println(totalSum);
        } else {
            if (minOdd == Integer.MAX_VALUE) { // 理论上不会发生
                System.out.println(0);
            } else {
                System.out.println(totalSum - minOdd);
            }
        }
    }
}

n = int(input())
nums = list(map(int, input().split()))

total_sum = sum(nums)

if total_sum % 2 == 0:
    print(total_sum)
else:
    min_odd = float('inf')
    found_odd = False
    for num in nums:
        if num % 2 != 0:
            min_odd = min(min_odd, num)
            found_odd = True
            
    if found_odd:
        print(total_sum - min_odd)
    else: # 理论上不会发生
        print(0)

算法及复杂度

算法：贪心
时间复杂度：我们只需要遍历一次输入的 $n$ 个元素来计算总和并找到最小奇数，因此时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：我们只用了常数个变量来存储总和与最小奇数，因此空间复杂度为 $\mathcal{O}(1)$ 。