题解 | #灵异背包？#

题目链接

灵异背包？

题目描述

给定 $n$ 个正整数 $a_1, a_2, \dots, a_n$ ，你可以任选其中若干个数放入一个“灵异背包”。要求背包内所有数之和为偶数，并且在这个前提下，和要尽可能大。

如果一个数也不选，则背包和为0。请输出可以获得的最大偶数和。

解题思路

这是一个基于奇偶性的贪心问题。我们的目标是获得最大的偶数和。

1. 从最大和出发 要使和尽可能大，我们最理想的情况是把所有的数都选上。设所有数的总和为 total_sum。现在我们基于这个最大可能的和进行分类讨论。

2. 分类讨论

情况一：total_sum 本身是偶数 如果所有数的总和本来就是偶数，那么这已经是我们能得到的最大和了，并且它满足条件。因此，直接选择所有数就是最优解。答案就是 total_sum。
情况二：total_sum 是奇数 如果总和是奇数，我们不能选择所有数。为了让和变为偶数，我们必须从总和中减去一个数（或者多个数），使得差为偶数。根据奇偶性运算法则：
- 奇数 - 奇数 = 偶数
- 奇数 - 偶数 = 奇数
要将奇数的总和变为偶数，我们必须从中减去一个奇数。为了让最终的和尽可能大，我们应该减去一个尽可能小的数。因此，最优策略是从原数集中找到那个最小的奇数，然后从总和中减去它。

所以，在这种情况下，答案是 total_sum - min_odd，其中 min_odd 是输入数据中最小的那个奇数。

3. 边界情况

如果输入的所有数都是偶数，那么它们的总和也必然是偶数，属于情况一。
如果 total_sum 是奇数，那么输入中必然至少存在一个奇数，所以我们总能找到一个 min_odd 来减去。
如果 total_sum 是奇数，且输入中只有一个数（它必然是奇数），那么减去 min_odd 之后，和就变成了0。这也是正确答案，因为它对应“一个数也不选”的情况。

算法步骤

初始化 total_sum 为0，min_odd 为一个极大的数。
遍历所有输入的数：
- 将当前数累加到 total_sum。
- 如果当前数是奇数，用它来更新 min_odd（min_odd = min(min_odd, current_num)）。
遍历结束后，检查 total_sum 的奇偶性。
如果 total_sum 是偶数，直接输出 total_sum。
如果 total_sum 是奇数，输出 total_sum - min_odd。

代码

c++
java
python

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n;
    cin >> n;
    
    long long total_sum = 0;
    long long min_odd = numeric_limits<long long>::max();
    
    for (int i = 0; i < n; ++i) {
        long long val;
        cin >> val;
        total_sum += val;
        if (val % 2 != 0) {
            min_odd = min(min_odd, val);
        }
    }
    
    if (total_sum % 2 == 0) {
        cout << total_sum << endl;
    } else {
        cout << total_sum - min_odd << endl;
    }
    
    return 0;
}

import java.util.Scanner;
import java.lang.Math;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        long totalSum = 0;
        long minOdd = Long.MAX_VALUE;
        
        for (int i = 0; i < n; i++) {
            long val = sc.nextLong();
            totalSum += val;
            if (val % 2 != 0) {
                minOdd = Math.min(minOdd, val);
            }
        }
        
        if (totalSum % 2 == 0) {
            System.out.println(totalSum);
        } else {
            System.out.println(totalSum - minOdd);
        }
    }
}

import sys

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    
    total_sum = sum(a)
    
    if total_sum % 2 == 0:
        print(total_sum)
    else:
        min_odd = float('inf')
        for x in a:
            if x % 2 != 0:
                min_odd = min(min_odd, x)
        print(total_sum - min_odd)

solve()

算法及复杂度

算法：贪心
时间复杂度：我们需要对输入的 $n$ 个数进行一次遍历，以计算总和并找到最小的奇数。因此，总时间复杂度为 $\mathcal{O}(n)$ 。
空间复杂度：在C++和Java的实现中，我们可以在读取数据的同时进行计算，只需要常数个额外变量，空间复杂度为 $\mathcal{O}(1)$ 。在Python的实现中，我们先将所有数读入列表，因此空间复杂度为 $\mathcal{O}(n)$ 。