分苹果 - 华为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和w3 = 6：3 = 011 5 = 101 6 = 110 --------------- XOR = 000上面的例子异或结果为 0，因此满足 A 的要求。
如果异或和不为 0，比如苹果权重变为
3, 5, 7：3 = 011 5 = 101 7 = 111 --------------- XOR = 001此时异或和为 1，表示这些苹果的重量组合无法让 A 达成要求。因此，B 无法在满足 A 的条件下分配苹果，只能输出 -1。
4. 总结
当异或和不为 0，说明没有任何可能的分法可以让 A 满足其二进制无进位加法的规则。因此，程序需要直接输出 -1，表示 A 的条件无法满足。在这种情况下，不论如何分配苹果，最终都无法实现 A 希望的异或结果为 0 的目标。
Java
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] weights = new int[n];
int xorSum = 0;
int totalSum = 0;
int minWeight = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
weights[i] = sc.nextInt();
xorSum ^= weights[i]; // 计算异或和
totalSum += weights[i]; // 计算苹果总重量
minWeight = Math.min(minWeight, weights[i]); // 找到最小的苹果重量
}
if (xorSum != 0) {
System.out.println(-1); // 如果异或和不为 0，无法满足 A 的要求
} else {
System.out.println(totalSum - minWeight); // A 选择最小的苹果，B 获得剩余的苹果
}
}
}
Python
def solve():
n = int(input())
weights = list(map(int, input().split()))
xor_sum = 0
total_sum = sum(weights) # 计算总重量
min_weight = min(weights) # 找到最小的苹果
for weight in weights:
xor_sum ^= weight # 计算异或和
if xor_sum != 0: # 如果异或和不为 0，无法满足 A 的要求
print(-1)
else:
print(total_sum - min_weight) # A 选择最小的苹果，B 获得剩余的苹果
solve()
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> weights(n);
int xorSum = 0;
int totalSum = 0;
int minWeight = INT_MAX;
for (int i = 0; i < n; i++) {
cin >> weights[i];
xorSum ^= weights[i]; // 计算异或和
totalSum += weights[i]; // 计算总重量
minWeight = min(minWeight, weights[i]); // 找到最小的苹果
}
if (xorSum != 0) {
cout << -1 << endl; // 无法满足 A 的要求
} else {
cout << totalSum - minWeight << endl; // A 选最小苹果，B 获得剩余的苹果
}
return 0;
}
#面经##秋招##华为od##华为od题库##华为od机试#整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
查看3道真题和解析