E卷-(100分)分苹果

分苹果

问题描述

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 < n; i++) {
        xor_sum ^= weights[i];
        total_sum += weights[i];
        if (weights[i] < min_weight) {
            min_weight = weights[i];
        }
    }
    
    // 如果异或和不为0，无法平均分配
    if (xor_sum != 0) {
        return -1;
    }
    
    // B 获得除最轻苹果外的所有苹果
    return total_sum - min_weight;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int