跳至主要內容

2025A-分苹果

题目描述与示例

题目描述

A，B两团体想把苹果分为两堆。

A盼望依照它的计算规则平分苹果，他的计算是依照二进制加法进行计算，而且不计算进位。

以12`` ``+`` ``5为例，按照A的计算规则有12 + 5 =`` ``bin``(1100``) ``+`` bin(``0101``) = bin(1001``)`` = 9 成立。

B的计算是最常见的十进制加法，包含进位。B期望在满足A的情形下获取苹果分量最多。

输入苹果的数目跟每个苹果的重量，输出满意A的情形下获取的苹果总重量；假如无法满意A的请求，输出-1。

题目练习网址：https://www.algomooc.com/problem/P4000

输入描述

苹果的数目跟每个苹果分量

输出描述

B在满意A的情形下获取的苹果总分量，假如B无法满意A的请求，输出-1。

示例一

输入

2
12 5

输出

-1

示例二

输入

2
12 12

输出

12

示例三

输入

3
3 5 6

输出

11

说明

按照A的计算方法 5 + 6 = 3 ，不进行二进制进位，bin(101)+ bin(110) = bin(011) = 3 。再按照B的方法计算，5 + 6 = 11。

解题思路

题干阅读理解

本题的题意非常费解，说人话就是：

  • 把数组apples分成两个部分apples1和apples2，分别作为A和B获得的苹果数。
  • 分别对apples1和apples2求异或和，得到xorsum1和xorsum2
  • xorsum1和xorsum2需要满足两者相等xorsum1 == xorsum2（即所谓的按照A的方法进行苹果平分）
  • 对apples1和apples2分别进行十进制求和，得到apples1_sum和apples2_sum。
  • 要求找到一种分苹果的方法，使得apples2_sum最大，作为B获得的苹果数。

如何满足A的分配规则

对于给定的任意一个数组apples，我们需要思考数组本身满足什么条件时，A的分配规则会得到满足。

由上一步的分析得知，如果A的分配规则满足，那么apples可以被分成apples1和apples2两部分，这两部分的异或和xorsum1和xorsum2满足两者相等的条件

xorsum1 == xorsum2

根据异或操作的性质，很容易得到

xorsum1 ^ xorsum2 == 0

如果把xorsum1和xorsum2分别展开并使用异或操作交换律，由于apples1和apples2正好组成了apples，我们可以得到

apples[0] ^ apples[2] ^ apples[1] ^ ... ^ apples[i] ^ ... ^ apples[n-1] == 0

上式的左边部分其实是apples数组的异或和。

换句话说，如果apples数组的异或和为0，那么apples数组一定可以拆成apples1和apples2两部分，满足A的分配规则。进一步地，无论apples拆成怎么样的两部分，都能够满足A的分配规则。

所以判断A的分配规则是否能满足的依据非常简单，即判断apples的异或和是否等于0即可。

如何贪心地让B获利

如果上述步骤想明白了，剩下的操作实际上非常简单了。由于无论apples拆成怎么样的两部分，都能够满足A的分配规则，为了让B尽可能多地获得苹果，我们只需要贪心地让A获得的那一部分apples1在十进制的数值上尽可能地小即可。A取最小的结果即为min(apples)，此时B获得的苹果数量为sum(apples) - min(apples)，即为答案。

上述核心思路整理成代码，实际上非常简短

xorsum = 0
for num in nums:
    xorsum ^= num

if xorsum == 0:
    print(sum(nums) - min(nums))
else:
    print(-1)

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频


n = int(input())
nums = list(map(int, input().split()))

# 初始化nums数组的异或和xorsum为0
xorsum = 0
# 遍历nums中的每一个元素num，计算所有num的异或和
for num in nums:
    xorsum ^= num

# 如果nums的异或和结果为0
# 说明nums可以按照A的方式进行分配
# 被分成两个部分分别分配给A和B
# 为了使得B获得的苹果数量尽可能地多
# 贪心地选择nums中的最小那个数分配给A
# 剩余所有苹果分配给B
if xorsum == 0:
    print(sum(nums) - min(nums))
# 如果nums的异或和结果不为0
# 则无法按照A的方式进行分配
else:
    print(-1)

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[] nums = new int[n];

        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }

        int xorsum = 0;
        for (int num : nums) {
            xorsum ^= num;
        }

        if (xorsum == 0) {
            int sum = 0;
            int min = Integer.MAX_VALUE;
            for (int num : nums) {
                sum += num;
                min = Math.min(min, num);
            }
            System.out.println(sum - min);
        } else {
            System.out.println(-1);
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);

    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    int xorsum = 0;
    for (int num : nums) {
        xorsum ^= num;
    }

    if (xorsum == 0) {
        int sum = 0;
        int min = INT_MAX;
        for (int num : nums) {
            sum += num;
            min = min < num ? min : num;
        }
        cout << sum - min << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}

C

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

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

    int nums[n]; // 苹果数组
    int xorsum = 0; // 初始化异或和
    int sum = 0; // 总和
    int minVal = INT_MAX; // 记录最小值

    // 读取苹果数组，并计算异或和、总和和最小值
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
        xorsum ^= nums[i];
        sum += nums[i];
        if (nums[i] < minVal) {
            minVal = nums[i];
        }
    }

    // 如果异或和为0，说明可以按照A的方式分配
    if (xorsum == 0) {
        printf("%d\n", sum - minVal);
    } else {
        printf("-1\n");
    }

    return 0;
}

Node JavaScript

const readline = require('readline');

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

// 读取输入
rl.question('', (n) => {
    n = parseInt(n.trim()); // 读取苹果个数
    rl.question('', (line) => {
        let nums = line.trim().split(' ').map(Number); // 读取苹果数组

        // 初始化异或和
        let xorsum = 0;
        // 遍历nums数组，计算所有数的异或和
        for (let num of nums) {
            xorsum ^= num;
        }

        // 如果异或和为0，说明可以按照A的方式分配
        if (xorsum === 0) {
            console.log(nums.reduce((a, b) => a + b, 0) - Math.min(...nums));
        } else {
            console.log(-1);
        }

        rl.close();
    });
});

Go

package main

import (
        "fmt"
        "math"
)

func main() {
        var n int
        fmt.Scan(&n)

        // 读取苹果数组
        nums := make([]int, n)
        for i := 0; i < n; i++ {
                fmt.Scan(&nums[i])
        }

        // 计算异或和
        xorsum := 0
        for _, num := range nums {
                xorsum ^= num
        }

        // 如果异或和为0，说明可以按照A的方式分配
        if xorsum == 0 {
                sum, minVal := 0, math.MaxInt32
                for _, num := range nums {
                        sum += num
                        if num < minVal {
                                minVal = num
                        }
                }
                fmt.Println(sum - minVal)
        } else {
                fmt.Println(-1)
        }
}

时空复杂度

时间复杂度：O(``N``)。仅需一次遍历数组。

空间复杂度：O(``1``)。仅需若干常数变量。

本站内容包括机考真题解析、八股文速记、技术&行为面试指南、真实上岸经验与截图墙。
Copyright © 2025 欧弟算法