分苹果 - 华为OD统一考试(E卷)

2024华为OD机试（E卷+D卷+C卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

A 和 B 两个人要分苹果。A 希望按照他的计算规则得到平均分配的苹果，而 B 希望在满足 A 的条件下获得尽可能多的苹果量。

A 的计算规则是按照二进制加法进行，并不计算进位。例如，12 + 5 = 9 （1100 + 0101 = 1001）。

B 的计算规则是正常的十进制加法，包括进位。

给定苹果的数量和每个苹果的重量，计算并满足 A 的要求的情况下，B 能获得的最大苹果总重量。如果无法满足 A 的要求，则输出 -1。

输入描述

第一行包含一个整数 n，表示苹果的数量。

第二行包含 n 个整数，表示每个苹果的重量 w1, w2, ..., wn。

输出描述

输出一个整数，表示 B 能获得的最大苹果总重量。如果无法满足 A 的要求，则输出 -1。

示例1

输入：
3
3 5 6

输出：
11

说明：
通过二进制无进位加法，A 要求的总重量是 3 XOR 5 XOR 6 = 0，B 能获得所有的苹果，总重量为 11。

示例2

输入：
8
7258 6579 2602 6716 3050 3564 5396 1773

输出：
35165

说明：
同样按照 A 的二进制无进位规则，B 获得最大的苹果重量为 35165。

题解

这道题是一道贪心算法题目，结合二进制无进位加法要求，逐个计算苹果的总重量是否满足 A 的计算规则。在满足 A 的要求下，B 能够获得的苹果总重量最大化。

解题思路：

• 首先计算所有苹果重量的异或和（即 A 的规则），判断这个值是否为 0。
• 如果异或和不为 0，表示无法满足 A 的要求，直接输出 -1。
• 如果异或和为 0，A 满足其要求，选择最小的一个苹果，剩余的全部苹果由 B 获得。输出 sum(weights) - min(weights)。

时间复杂度：O(n)，因为我们需要遍历苹果的重量进行 XOR 运算和求和。

空间复杂度：O(1)，只需使用常量的辅助空间。

如果异或和不为 0，表示无法满足 A 的要求，直接输出 -1。这背后的原理可以从 二进制无进位加法（即异或操作）的特性出发详细解释。

1. 二进制无进位加法（XOR 操作）

在这个题目中，A 希望通过异或操作进行“无进位加法”，也就是在二进制中，将两个数逐位进行比较，当两位相同（0 XOR 0 或 1 XOR 1）时，结果为 0；当两位不同（0 XOR 1 或 1 XOR 0）时，结果为 1。例如：

• 12 (1100) 和 5 (0101) 的异或结果是 9 (1001)。

异或操作有一个非常重要的性质：

• 自反性：任何数和自身异或都等于 0，即 x ^ x = 0。
• 交换律和结合律：a ^ b ^ c 等价于 a ^ (b ^ c)，而且可以随意交换操作顺序。

2. 满足 A 要求的条件

A 的目标是：希望多个苹果的重量通过异或操作得到一个结果 0。为了实现这一目标，苹果的权重组合必须满足这样的条件：这些权重通过异或操作的结果为 0。如果异或的总和不为 0，则无法找到满足 A 要求的苹果分配方案。

• 假设有 n 个苹果，每个苹果的重量为 w1, w2, ..., wn。A 希望 w1 ^ w2 ^ ... ^ wn = 0。
• 如果这个异或总和不为 0，意味着无论怎么分配苹果，总是无法在不进位的情况下让 A 的计算规则满足。

3. 为什么 XOR 和不为 0 说明无法满足 A 的要求

当所有苹果的异或总和不为 0 时，表示这些数之间在二进制的某些位上不平衡，A 希望的“无进位加法”无法达成。

例如，考虑苹果权重为 w1 = 3、w2 = 5 和 ：