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 weights[20000];  // 最大可能的苹果数量
    for (int i = 0; i < n; i++) {
        scanf("%d", &weights[i]);
    }
    
    int result = max_apples_for_b(n, weights);
    printf("%d\n", result);
    
    return 0;
}

• Javascript

function maxApplesForB(n, weights) {
    // 计算所有苹果重量的异或和
    let xorSum = 0;
    for (let w of weights) {
        xorSum ^= w;
    }

    // 如果异或和不为0，无法平均分配
    if (xorSum !== 0) {
        return -1;
    }

    // 找出最轻的苹果
    let minWeight = Math.min(...weights);

    // B 获得除最轻苹果外的所有苹果
    return weights.reduce((acc, curr) => acc + curr, 0) - minWeight;
}

// 读取输入
const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.question('', (n) => {
    rl.question('', (weightsInput) => {
        const weights = weightsInput.split(' ').map(Number);
        const result = maxApplesForB(parseInt(n), weights);
        console.log(result);
        rl.close();
    });
});

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] weights = new int[n];
        for (int i = 0; i < n; i++) {
            weights[i] = scanner.nextInt();
        }
        System.out.println(maxApplesForB(n, weights));
    }

    private static int maxApplesForB(int n, int[] weights) {
        int xorSum = 0;
        int totalSum = 0;
        int minWeight = Integer.MAX_VALUE;
        
        // 计算异或和、总和和最小重量
        for (int w : weights) {
            xorSum ^= w;
            totalSum += w;
            minWeight = Math.min(minWeight, w);
        }
        
        // 如果异或和不为0，无法平均分配
        if (xorSum != 0) {
            return -1;
        }
        
        // B 获得除最轻苹果外的所有苹果
        return totalSum - minWeight;
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int max_apples_for_b(int n, vector<int>& weights) {
    int xor_sum = 0;
    int total_sum = 0;
    int min_weight = INT_MAX;
    
    // 计算异或和、总和和最小重量
    for (int w : weights) {
        xor_sum ^= w;
        total_sum += w;
        min_weight = min(min_weight, w);
    }
    
    // 如果异或和不为0，无法平均分配
    if (xor_sum != 0) {
        return -1;
    }
    
    // B 获得除最轻苹果外的所有苹果
    return total_sum - min_weight;
}

int main() {
    int n;
    cin >> n;
    
    vector<int> weights(n);
    for (int i = 0; i < n; i++) {
        cin >> weights[i];
    }
    
    cout << max_apples_for_b(n, weights) << endl;
    
    return 0;
}