【最新华为OD机试E卷】分苹果(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解

🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目正在持续上线中~

最新华为OD机试专栏: https://www.nowcoder.com/creation/manager/columnDetail/MgbyJj

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

🍎 分苹果

问题描述

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

A 的计算规则是按照二进制加法计算，并且不计算进位。例如，（）。

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

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

输入格式

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

第二行包含 个整数，表示每个苹果的重量 。

输出格式

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

样例输入

3
3 5 6

样例输出

11

样例解释

A 得到重量为 3 的苹果，B 得到重量为 5 和 6 的苹果。 3 和 (5+6) 的二进制无进位加法结果相等：。 B 获得的总重量为 。

样例输入

8
7258 6579 2602 6716 3050 3564 5396 1773

样例输出

35165

数据范围

• 
• ，其中 表示第 个苹果的重量

题解

这道题目的关键在于理解 A 的计算规则实际上就是异或运算（XOR）。

解题思路如下：

1. 计算所有苹果重量的异或和。如果结果不为 0，说明无法满足 A 的要求，直接返回 -1。

2. 如果异或和为 0，说明可以平均分配（在 A 的规则下）。此时，B 应该尽可能多地获取重量大的苹果。

3. 最优策略是让 A 获得最轻的苹果，B 获得剩下的所有苹果。这是因为异或和为 0 的情况下，剩下的苹果的异或和必然等于最轻苹果的重量。

4. 因此，只需要找出最轻的苹果，将其重量从总重量中减去，剩下的就是 B 能获得的最大重量。

时间复杂度分析：这个算法只需要遍历一遍数组，时间复杂度为 ，对于给定的数据范围（）是完全可以接受的。

参考代码

• Python

def max_apples_for_b(n, weights):
    # 计算所有苹果重量的异或和
    xor_sum = 0
    for w in weights:
        xor_sum ^= w
    
    # 如果异或和不为0，无法平均分配
    if xor_sum != 0:
        return -1
    
    # 找出最轻的苹果
    min_weight = min(weights)
    
    # B 获得除最轻苹果外的所有苹果
    return sum(weights) - min_weight

# 读取输入
n = int(input())
weights = list(map(int, input().split()))

# 计算并输出结果
result = max_apples_for_b(n, weights)
print(result)

• C

#include <stdio.h>
#include <limits.h>

int max_apples_for_b(int n, int weights[]) {
    int xor_sum = 0;
    int total_sum = 0;
    int min_weight = INT_MAX;
    
    // 计算异或和、总和和最小重量
    for (int i = 0; i