小酷宝的灵异背包C++ 时间限制: 1.0 Sec 内存限制: 128 MB 提交: 0 解决: 192 [提交] [状态] [讨论版] [命题人: 外部导入] 难度 题目描述 小酷宝是个聪明伶俐的孩子，对数字有着天生的敏感和喜爱。当他听说这个关于灵异背包和正整数的挑战时，眼睛里闪烁着好奇和兴奋的光芒。 灵异背包可以装下无限的数，但是得保证放进去的数的总和必须为偶数。 小酷宝首先仔细审视了眼前的n个正整数，他的小脑袋里飞快地转动着，思考如何选择其中一些数放进灵异背包中，使得背包里面所有数的总和为偶数且最大，能得到的最大值是多少？ 小酷宝开始尝试不同的组合，他用手中的小木棍代表这些数字，在沙地上摆出各种可能的排列。 他注意到，如果两个奇数相加，结果会是偶数；而两个偶数相加，结果仍然是偶数。 这给了他一个启示：他可以通过选择全部的偶数和选择适当的奇数，来构建出最大的偶数总和。 注意：如果你不将任何数放进灵异背包，此时背包总和为0 输入 第一行包含一个正整数 n（1≤n≤105)，表示数字的数量 接下来n行包含n个正整数 a1,a2…,an (1≤ai≤2×104)，表示数字的大小 输出 输出一个整数，表示灵异背包所有数的总和为偶数且最大是多少 样例输入1 复制 3 2 5 6 样例输出1 复制 8 样例输入2 复制 1 3 样例输出2 复制 0 提示 样例解释1 当灵异背包里面有(2,5,6)，此时总和为2+5+6=13，为奇数，不满足条件 当灵异背包里面有(2,6)，此时总和为2+6=8，为偶数，且为最大值 样例解释2 选择的灵异背包为空，总和为0

<think>嗯，这个问题看起来有点挑战性。我需要仔细理解题目要求。题目是说，小酷宝有一个背包，可以装任意数量的数，但总和必须是偶数，而且要尽可能大。如果无法满足总和为偶数，就输出0。首先，我得想清楚怎么处理这些数，使得总和最大且为偶数。 首先，我应该考虑所有数的总和。如果总和本身就是偶数，那么直接取所有数就可以了。但如果是奇数，就需要调整，可能需要去掉一个最小的奇数。因为奇数和奇数的和是偶数，所以如果总和是奇数，说明总共有奇数个奇数。这时候，去掉最小的那个奇数，剩下的总和就会变成偶数。不过，这里可能还有其他情况需要考虑，比如是否存在奇数。 举个例子，假设总和是奇数，这时候要看有没有奇数。如果有奇数的话，去掉最小的那个；如果没有，那就不可能得到偶数和，只能输出0。但题目里每个数都是正整数，所以如果总和是奇数，必须至少有一个奇数，否则总和不可能是奇数。因为所有偶数相加的和还是偶数，只有当有奇数个奇数时，总和才会是奇数。所以在这种情况下，应该找到所有数中的奇数，然后去掉最小的那个，剩下的总和就是最大的偶数。 不过，可能还有一种情况：如果所有的数都是奇数，并且数量是奇数个，那么去掉一个最小的奇数后，剩下的数量是偶数个，它们的和就是偶数。但如果总和是奇数，并且有奇数和偶数，那处理方式一样，就是总和减去最小的奇数。但是如果总和已经是偶数，就直接输出总和。 那具体步骤应该是这样的： 1. 计算所有数的总和。 2. 统计所有奇数的数量，并找到最小的那个奇数。 3. 如果总和是偶数，直接输出总和。 4. 如果总和是奇数： a. 如果存在奇数，那么总和减去最小的奇数。 b. 如果没有奇数（这种情况不可能，因为总和是奇数，必须有奇数个奇数），所以不可能，这时候输出0。 5. 但是还要注意，如果总和减去最小的奇数之后的结果是否是正数。比如，如果只有一个奇数，且总和就是这个奇数，那么减去之后总和是0，这时候是否合法？题目说明，允许不选任何数，此时总和为0，但可能更大的情况是否存在？ 比如样例输入2的情况：输入是3，总和是3，奇数。这时候没有其他数，所以只能不选，输出0。这种情况下，虽然总和是3，但无法满足条件，所以必须输出0。因此，当总和是奇数时，如果存在奇数，那么总和减去最小的奇数的结果是否大于等于0？比如，总和是奇数，且总和减去最小的奇数后是否可能为0？这个时候应该取最大值，如果总和减去奇数后是0，那么是否要选择不取任何数？ 比如，假设总和是3，此时总和是奇数。最小的奇数是3，总和-3=0。此时有两种选择：选0或者不选任何数，两种情况都是0。所以这个时候应该输出0。所以，在总和为奇数的情况下，必须检查总和减去最小的奇数是否大于0。如果结果是0，那么是否可以选择？题目说明，允许总和为0的情况，即不选任何数，但此时总和是0，而如果总和减去奇数后的结果是0，则可以选择那个情况，但此时总和为0，和直接不选结果一样。所以在这种情况下，应该比较两种情况，取最大的。或者，总和减去奇数的结果如果是正数，就取；否则取0。 那如何处理？ 例如，当总和是奇数，并且存在奇数的时候，总和减去最小的奇数的结果是否为偶数？ 是的，因为总和是奇数，奇数减去奇数是偶数，所以结果肯定是偶数。但是否可能总和减去最小的奇数后的结果是0？比如，当只有一个奇数，且总和就是这个奇数的时候。例如，样例输入2中的情况，此时总和是3，减去3得到0，这是合法的。但是题目允许总和为0的情况，所以此时输出0是正确的。 所以处理步骤应该是： 总和如果是偶数，直接输出。 如果是奇数： 如果存在奇数，则总和减去最小的奇数，如果结果大于等于0，输出该结果；否则输出0。 但如何确定是否有奇数存在？因为总和是奇数的前提是奇数的数量是奇数。所以如果总和是奇数，那么奇数的数量至少是1。因此，当总和是奇数时，一定存在奇数，所以可以安全地减去最小的奇数。这样结果一定是偶数。但需要考虑总和减去这个奇数后的结果是否为0的情况。例如，当所有数的总和等于那个最小的奇数的时候，比如只有一个数，比如样例输入2的情况。这时候总和减去这个数等于0，此时输出0。 所以，这种情况下，总和减去最小的奇数的结果可能为0，但题目允许这种情况，因为总和是0是偶数，所以应该输出这个结果。 比如，样例输入2中的总和是3，减去最小的奇数3，得到0，所以输出0，这符合题目要求。 那另一个情况：如果总和是奇数，且总和减去最小的奇数的结果大于0，则输出该结果；否则输出0。但实际上，只要总和是奇数，并且存在奇数，那么总和减去最小的奇数后的结果可能为0或者更大。例如，假设总和是5，且有一个奇数是3，其他都是偶数。总和5是奇数，减去最小的奇数3得到2，所以输出2。如果总和是3，减去3得到0，输出0。 所以正确的处理步骤应该是： 计算总和sum。 如果sum是偶数，输出sum。 否则： 找出所有奇数中的最小值min_odd。 如果sum - min_odd >=0 → 输出sum - min_odd. 否则，输出0. 但是sum是总和，所以sum - min_odd至少等于sum - min_odd的最小可能是什么？比如，sum是min_odd本身的时候，sum - min_odd=0。所以只要sum是奇数，那么sum - min_odd的结果是sum - min_odd，可能为0或者更大的数。这时候需要判断是否sum - min_odd >=0？其实sum肯定大于等于min_odd吗？ 例如，sum是所有数的总和，而min_odd是其中一个数。所以sum >= min_odd。所以sum - min_odd >=0是肯定的。因此，在这种情况下，不管怎样，sum - min_odd是可行的。所以当sum是奇数时，输出sum - min_odd即可。 但比如样例输入2的情况，sum=3，min_odd=3，sum - min_odd=0，此时输出0，正确。另一个例子，sum=5，min_odd=3，那么sum - min_odd=2，是偶数，正确。 那这样，逻辑是： 如果总和是偶数→输出总和。 否则→总和减去最小的奇数。 但需要注意，如果总和减去最小的奇数后的结果是0的话，是否符合题目要求？题目允许总和为0，所以没问题。 那现在的问题是，如何找到最小的奇数？ 如果总和是奇数，那么奇数的数量必须是奇数个。所以必须存在至少一个奇数。所以当sum是奇数时，必然存在至少一个奇数。所以可以安全地取最小的奇数。 所以，算法的步骤是： 1. 计算所有数的总和sum。 2. 统计所有奇数，并找到其中最小的那个min_odd。 3. 如果sum是偶数，输出sum。 4. 否则，如果存在奇数（必然存在），输出sum - min_odd。 但需要注意，当sum - min_odd是否会导致总和为0的情况？例如，当所有数之和是min_odd的时候，比如只有一个奇数。此时输出0，正确。 那现在如何处理？ 例如，对于样例输入1： 3个数是2、5、6。总和是2+5+6=13，是奇数。奇数是5。最小的奇数是5。总和减去5是8，所以输出8。正确。 样例输入2：总和是3，奇数。最小的奇数是3。总和-3=0，输出0。正确。 另一个例子，比如输入是n=2，数组是1和3。总和是4，是偶数。所以直接输出4？或者总和是4？是的，正确。那总和是偶数，直接输出。 另一个测试案例，输入是n=4，数组是3、5、7、9。总和是24，偶数。输出24？是的。但如果总和是23（比如有一个数少1），那么sum是23，奇数。此时最小的奇数是3。sum -3=20，输出20。 所以逻辑是正确的。 那么现在需要考虑如何高效地找到最小的奇数。因为n可能达到1e5，所以需要线性扫描数组，记录最小的奇数。 实现步骤： - 遍历所有数，计算总和sum。 - 同时，遍历时记录所有奇数，并找到最小的那个。 - 最后，根据总和是否为偶数，决定输出sum或者sum - min_odd。 如果总和是奇数，并且存在奇数，则sum - min_odd一定是一个非负的偶数。而如果总和是奇数但没有奇数的话，这不可能，因为总和的奇偶性由奇数的个数的奇偶性决定。所以当sum是奇数时，必定存在奇数。 所以代码的大致结构： 输入n。 输入n个数，保存到数组或者直接处理。 计算sum，同时找出所有奇数中的最小值min_odd. 如果sum是偶数，输出sum. 否则，输出sum - min_odd. 但要注意，当sum - min_odd的结果为0的时候是否允许？题目允许背包为空，总和为0，所以没问题。 但是，假设所有数都是偶数，那么总和一定是偶数，所以这种情况会被sum是偶数的情况处理。 例如，输入n=3，三个数都是偶数。总和是偶数，直接输出总和。 另一个情况，输入n=2，两个奇数。sum是偶数，所以输出总和。 那现在，如何处理没有奇数的情况？例如，所有数都是偶数，那么总和一定是偶数，所以直接输出总和。没有问题。 综上，代码的思路是正确的。 现在，测试样例输入2的情况： 输入n=1，数是3。sum=3，奇数。此时，min_odd=3. sum -3=0，正确。 另一个样例输入1，总和13是奇数，min_odd=5，13-5=8，正确。 所以代码逻辑正确。 现在，编写代码： 用C++的话，需要注意数据范围。n是1e5，每个数最大是2e4，总和可能到1e5*2e4=2e9，这在int范围内可能不够。需要用long long类型存储总和。 所以，代码的大致结构： #include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; long long sum = 0; int min_odd = INT_MAX; // 初始化为很大的数 bool has_odd = false; for (int i = 0; i < n; ++i) { int num; cin >> num; sum += num; if (num % 2 != 0) { has_odd = true; if (num < min_odd) { min_odd = num; } } } if (sum % 2 == 0) { cout << sum << endl; } else { if (has_odd) { cout << sum - min_odd << endl; } else { cout << 0 << endl; } } return 0; } 但是这里有个问题：当sum是奇数时，has_odd可能为true吗？ 因为当sum是奇数时，奇数的数量必须是奇数个，所以此时至少有一个奇数。所以在这种情况下，has_odd一定为true。所以在else分支中，可以省略判断has_odd的情况。 比如，当sum是奇数时，必然存在至少一个奇数。所以在else块中，可以安全地输出sum - min_odd. 所以代码可以优化： 在计算sum的时候，记录所有奇数的最小值。如果sum是奇数，那么必然存在奇数，所以min_odd已经被找到。 所以修改后的代码如下： #include <iostream> #include <climits> // 为了使用INT_MAX using namespace std; int main() { int n; cin >> n; long long sum = 0; int min_odd = INT_MAX; // 初始化为最大值 for (int i = 0; i < n; ++i) { int num; cin >> num; sum += num; if (num % 2 == 1) { // 如果是奇数 if (num < min_odd) { min_odd = num; } } } if (sum % 2 == 0) { cout << sum << endl; } else { // sum是奇数，此时必须存在至少一个奇数 cout << sum - min_odd << endl; } return 0; } 这样更简洁。例如，样例输入2的情况，sum=3是奇数，min_odd=3，输出3-3=0，正确。 另一个情况，假设所有数都是偶数，sum是偶数，直接输出sum。正确。 如果sum是奇数，并且存在多个奇数，那么sum - 最小的奇数的结果正确。 所以这个代码应该可以处理所有情况。 需要注意的是，如果所有数都是偶数，sum是偶数，此时min_odd没有被更新，仍然是INT_MAX。但在这种情况下，sum是偶数，所以不会进入else分支，所以没有问题。 例如，当n=3，数组是2,4,6。sum=12，是偶数，直接输出12。此时min_odd还是INT_MAX，但不会影响结果，因为不需要使用它。 所以这个代码是正确的。</think>### 方法思路 要解决这个问题，我们需要找到一组数的最大偶数和。关键在于如何处理奇数和偶数的组合，使得总和为偶数且最大。 #### 核心思路 1. **计算总和**：首先计算所有数字的总和。 2. **奇偶判断**：若总和为偶数，直接输出总和。 3. **调整奇数和**：若总和为奇数，则减去最小的奇数，使其变为偶数。若不存在奇数（此时总和必为偶数），直接输出总和。 ### 解决代码 ```cpp #include <iostream> #include <climits> using namespace std; int main() { int n; cin >> n; long long sum = 0; int min_odd = INT_MAX; // 初始化最小奇数为最大值 for (int i = 0; i < n; ++i) { int num; cin >> num; sum += num; if (num % 2 == 1 && num < min_odd) { // 当前数为奇数且更小 min_odd = num; } } if (sum % 2 == 0) { cout << sum << endl; } else { // 总和为奇数时，必然存在至少一个奇数 cout << (sum - min_odd) << endl; } return 0; } ``` ### 代码解释 1. **输入处理**：读取数字数量 `n` 和每个数字的值。 2. **总和与最小奇数计算**：遍历所有数字，计算总和，并记录最小的奇数。 3. **奇偶判断与结果输出**： - 若总和为偶数，直接输出。 - 若总和为奇数，减去最小的奇数得到最大偶数和。 该方法时间复杂度为 $O(n)$，空间复杂度为 $O(1)$，适用于题目给定的数据规模。