华为OD机试2025A卷-分苹果[100分]（Java_Python3_C++_C语言_JsNode）实现100%通过率

前言

华为OD机试2025A卷 是华为外包岗位招聘中机试环节的题目集合，其中"分苹果"是一道经典的位运算（异或）题目。本题考察的是二进制不进位加法即异或运算的性质，以及在满足约束下求最优分配的贪心思想。题目分值100分，难度较低，只要识破"二进制不进位加法就是异或"这一转化，整道题就是一次线性扫描。本文将提供5种语言的完整实现（C++、Java、Python3、C语言、JavaScript），每种语言的代码都附带详细的中文注释，帮助读者彻底理解异或判定与贪心分配的建模与求解过程。建议在阅读代码时，重点关注总异或和是否为 0 的判定，以及为什么取最轻的苹果分给 A。

一：题目描述

分苹果

题目名称：分苹果

【题目描述】

A、B 两个人把苹果分为两堆，A 希望按照他的计算规则等分苹果，他的计算规则是按照二进制加法计算，并且不计算进位（如 12 + 5 = 9，即 1100 + 0101 = 1001）；B 的计算规则是十进制加法，包括正常进位，B 希望在满足 A 的情况下获取苹果重量最多。

输入苹果的数量和每个苹果重量，输出满足 A 的情况下 B 获取的苹果总重量。如果无法满足 A 的要求，输出 -1。

【输入格式】

第一行是苹果数量，第二行是每个苹果的重量（用空格分隔）：

1 ≤ 总苹果数量 ≤ 20000
1 ≤ 每个苹果重量 ≤ 10000

【输出格式】

输出一行，表示在满足 A 的分堆规则下 B 能获取的苹果总重量；若无法满足 A 的要求，输出 -1。

【示例1】

输入：

3
3 5 6

输出：

11

解释：三个苹果重量为 3、5、6。按二进制不进位加法（即异或），5 ⊕ 6 = 3，于是把 {5,6} 给 B、{3} 给 A 即可满足 A 的等分规则，此时 B 拿到 5+6=11，是所有合法分法中 B 的最大重量。

【示例2】

输入：

8
7258 6579 2602 6716 3050 3564 5396 1773

输出：

35165

解释：先求全部苹果的异或和，结果为 0，说明可以按 A 的规则分成两堆。总重量为 36838，把最轻的苹果 1773 单独分给 A，其余全部归 B，B 的最大重量为 36838 – 1773 = 35165。

二：解题思路

解法一：暴力枚举所有分堆（不推荐）

暴力思路是枚举每个苹果"给 A 还是给 B"，共 2^n 种子集划分，对每种划分分别计算两堆的异或和，判断是否相等，再在所有合法划分中取 B 堆重量最大者。当 n = 20000 时，枚举量是天文数字，完全无法在限定时间内完成。因此必须利用异或的数学性质把问题降到 O(n)。

解法二：异或和判定 + 取最轻（最优解）

核心建模：二进制不进位加法就是异或

"A 的规则"是按二进制加法但不进位，逐位相加：0+0=0, 0+1=1, 1+0=1, 1+1=0，这正是**按位异或（XOR）**的定义。于是"两堆苹果按 A 的规则相等"等价于：

堆 A 的异或和 == 堆 B 的异或和

为什么先算全体异或和

设所有苹果的异或和为 total = xorA ⊕ xorB。若两堆相等 xorA == xorB，则 xorA ⊕ xorB = 0，即 total == 0。这是能分堆的必要条件：

• 若 total != 0，两堆异或和不可能相等，直接输出 -1。
• 若 total == 0，则一定存在合法分法。

怎么让 B 拿最多

B 想让自己那堆总重量最大，等价于让 A 那堆总重量最小。当 total == 0 时，把最轻的那个苹果单独作为 A 堆、其余全部作为 B 堆即可：因为 total = min ⊕ xorB = 0，所以 xorB = min = xorA，两堆天然相等。这样 A 堆只有最轻的一个苹果，B 堆自然拿到了除它之外的全部重量，即 总重量 – 最轻重量。

实际步骤总结：

三：代码实现

C++

#include <iostream>
#include <vector>
#include <limits>

int main() {
int n;
// 读取苹果的数量 n
std::cin >> n;
// 创建一个大小为 n 的向量，用于存储每个苹果的重量
std::vector<int> a(n);
// 循环读取每个苹果的重量，并存储到向量中
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
// 初始化异或总和变量
int sums = 0;
// 初始化最小值变量为整型的最大值
int min = std::numeric_limits<int>::max();
// 遍历所有苹果的重量
for (int x : a) {
// 按位异或操作，更新异或总和
sums = sums ^ x;
// 找到当前最小的苹果重量
if (x < min) {
min = x;
}
}
// 如果异或总和不为 0，则无法按 A 的规则分堆，输出 -1
if (sums != 0) {
std::cout << –1 << std::endl;
} else {
// 计算所有苹果重量的总和
int sum = 0;
for (int x : a) {
sum += x;
}
// 输出 B 可以获取的最大苹果重量（总和减去最小的苹果重量）
std::cout << sum – min << std::endl;
}
return 0;
}

Java

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
// 创建一个扫描器对象，用于读取输入
Scanner scanner = new Scanner(System.in);
// 读取苹果的数量 n
int n = scanner.nextInt();
// 创建一个大小为 n 的数组，用于存储每个苹果的重量
int[] a = new int[n];
// 循环读取每个苹果的重量，并存储到数组中
for (int i = 0; i < n; i++) {
a[i] = scanner.nextInt();
}
// 初始化异或总和变量
int sums = 0;
// 初始化最小值变量为整型的最大值
int min = Integer.MAX_VALUE;
// 遍历所有苹果的重量
for (int x : a) {
// 按位异或操作，更新异或总和
sums = sums ^ x;
// 找到当前最小的苹果重量
if (x < min) {
min = x;
}
}
// 如果异或总和不为 0，则无法按 A 的规则分堆，输出 -1
if (sums != 0) {
System.out.println(–1);
} else {
// 计算所有苹果重量的总和
int sum = 0;
for (int x : a) {
sum += x;
}
// 输出 B 可以获取的最大苹果重量（总和减去最小的苹果重量）
System.out.println(sum – min);
}
}
}

Python3

import sys

# 读取苹果的数量 n
n = int(input())
# 读取每个苹果的重量并存储到列表 a 中
a = list(map(int, input().split()))

# 初始化异或总和
sums = 0
# 初始化最小值为系统的最大整数
min_val = sys.maxsize
# 遍历所有苹果的重量
for x in a:
# 按位异或操作，更新异或总和
sums = sums ^ x
# 找到当前最小的苹果重量
if x < min_val:
min_val = x

# 如果异或总和不为 0，则无法按 A 的规则分堆，输出 -1
if sums != 0:
print(–1)
else:
# 计算所有苹果重量的总和
total_sum = sum(a)
# 输出 B 可以获取的最大苹果重量（总和减去最小的苹果重量）
print(total_sum – min_val)

C语言

#include <stdio.h>
#include <limits.h> // 用于定义整型的最大值 INT_MAX

int main() {
int n;
// 读取苹果的数量 n
scanf("%d", &n);

// 创建一个大小为 n 的数组，用于存储每个苹果的重量
int a[n];

// 循环读取每个苹果的重量，并存储到数组中
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}

// 初始化异或总和变量
int sums = 0;
// 初始化最小值变量为整型的最大值
int min = INT_MAX;

// 遍历所有苹果的重量
for (int i = 0; i < n; i++) {
// 按位异或操作，更新异或总和
sums = sums ^ a[i];
// 找到当前最小的苹果重量
if (a[i] < min) {
min = a[i];
}
}

// 如果异或总和不为 0，则无法按 A 的规则分堆，输出 -1
if (sums != 0) {
printf("-1\\n");
} else {
// 计算所有苹果重量的总和
int sum = 0;
for (int i = 0; i < n; i++) {
sum += a[i];
}
// 输出 B 可以获取的最大苹果重量（总和减去最小的苹果重量）
printf("%d\\n", sum – min);
}

return 0;
}

JavaScript

const readline = require('readline');

const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});

let n; // 苹果数量
let a; // 每个苹果的重量数组

// 读取输入的第一行，苹果数量 n
rl.on('line', (inputN) => {
n = parseInt(inputN);

// 读取输入的第二行，苹果的重量列表
rl.on('line', (inputA) => {
a = inputA.split(' ').map(Number);

// 初始化异或总和
let sums = 0;
// 初始化最小值为 JavaScript 中安全的最大整数
let min_val = Number.MAX_SAFE_INTEGER;

// 遍历所有苹果的重量
a.forEach((x) => {
// 按位异或操作，更新异或总和
sums = sums ^ x;
// 找到当前最小的苹果重量
if (x < min_val) {
min_val = x;
}
});

// 如果异或总和不为 0，则无法按 A 的规则分堆，输出 -1
if (sums !== 0) {
console.log(–1);
} else {
// 计算所有苹果重量的总和
const total_sum = a.reduce((sum, x) => sum + x, 0);
// 输出 B 可以获取的最大苹果重量（总和减去最小的苹果重量）
console.log(total_sum – min_val);
}

rl.close(); // 关闭读取接口
});
});

四：复杂度分析

五：易错点