当前位置：首页 > article >正文

【华为OD-E卷 - 分积木 100分（python、java、c++、js、c）】

article 2025/2/1 5:09:11

【华为OD-E卷 - 分积木 100分（python、java、c++、js、c）】

题目

Solo和koko是两兄弟，妈妈给了他们一大堆积木，每块积木上都有自己的重量。
现在他们想要将这些积木分成两堆。
哥哥Solo负责分配，弟弟koko要求两个人获得的积木总重量“相等”（根据Koko的逻辑），个数可以不同，不然就会哭，但koko只会先将两个数转成二进制再进行加法，而且总会忘记进位（每个进位都忘记）。
如当25（11101）加11（01011）时，koko得到的计算结果是18（10010）
11001 +01011
10010 Solo想要尽可能使自己得到的积木总重量最大，且不让koko哭

输入描述

第一行是一个整数N，表示有多少块积木；

2 ≤ N ≤ 100 第二行为空格分开的N个整数Ci，表示第i块积木的重量。

1 ≤ Ci ≤ 10^6

输出描述

如果能让koko不哭，输出Solo所能获得积木的最大总重量；否则输出“NO”

用例

用例一：

输入：

3
3 5 6

输出：

python解法

解题思路：
问题描述：

给定一个长度为 n 的整数数组 blocks。
判断是否可以将数组划分为两个或多个子数组，使得这些子数组的 XOR 和为 0。
如果可以，返回数组的总和减去最小值；否则返回 “NO”。
数学基础：

XOR 操作的性质：
a ^ a = 0：任何数字与自身异或结果为 0。
a ^ 0 = a：任何数字与 0 异或结果为数字本身。
XOR 满足交换律和结合律：a ^ b ^ c = c ^ b ^ a。
划分条件：
如果整个数组的 XOR 和 xor_sum 不为 0，则无法划分为 XOR 和为 0 的子数组。
如果 xor_sum = 0，则划分可能存在。具体返回的值与数组的最小值有关。
实现步骤：

计算总和与 XOR 和：
遍历数组，计算数组的总和 total_sum 和 XOR 和 xor_sum。
判断 XOR 和：
如果 xor_sum != 0，返回 “NO”。
如果 xor_sum = 0，说明可以划分，返回 total_sum - min(blocks)。
核心逻辑：
XOR 和为 0 是判断是否能划分的充分条件。
返回 total_sum - min(blocks) 是基于划分后最大化子数组和的策略。
时间复杂度：

总时间复杂度：O(n)，遍历数组两次，分别计算总和、XOR 和及最小值。
空间复杂度：O(1)，仅使用常量额外空间

def divide_blocks(n, blocks):
    """
    判断是否可以将数组划分为 XOR 和为 0 的子数组。
    如果可以，返回 total_sum - min(blocks)，否则返回 "NO"。

    :param n: 数组长度
    :param blocks: 数组
    :return: 可划分时的值或 "NO"
    """
    # 计算数组的总和
    total_sum = sum(blocks)
    # 计算数组的 XOR 和
    xor_sum = 0
    for block in blocks:
        xor_sum ^= block

    # 如果 XOR 和不为 0，无法划分，返回 "NO"
    if xor_sum != 0:
        return "NO"
    
    # 如果 XOR 和为 0，返回 total_sum - 最小值
    return total_sum - min(blocks)


# 读取输入
n = int(input())  # 数组长度
blocks = list(map(int, input().split()))  # 数组元素
# 输出结果
print(divide_blocks(n, blocks))

java解法

解题思路
问题描述：

给定一个整数数组 weightArray，需要判断是否可以将数组划分为多个部分，使得这些部分的 XOR 和为 0。
如果可以，返回数组总和减去最小值；如果不能，返回 “NO”。
关键点分析：

XOR 的性质：
a ^ a = 0：任何数与自身异或结果为 0。
a ^ 0 = a：任何数与 0 异或结果为自身。
XOR 满足交换律和结合律。
划分条件：
如果整个数组的 XOR 和不为 0，无法划分为 XOR 和为 0 的部分。
如果 XOR 和为 0，可以划分为满足条件的部分。
优化策略：

将数组排序，最小值单独处理（通过最小值控制总和）。
总和 correctTotal 初始化为最小值，用于计算数组总和。
XOR 和 xorSum 初始化为最小值，用于计算整个数组的 XOR 值。
实现步骤：

排序数组：
先对数组进行排序，使最小值在数组的第一个位置。
计算总和和 XOR 和：
遍历数组，逐步计算总和 correctTotal 和 XOR 和 xorSum。
判断 XOR 和：
如果 XOR 和为 0，返回 correctTotal - smallest。
如果 XOR 和不为 0，返回 “NO”。
时间复杂度：

数组排序：O(n log n)。
遍历计算总和和 XOR 和：O(n)。
总时间复杂度：O(n log n)。

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 输入数组大小
        int size = scanner.nextInt();
        int[] weightArray = new int[size];
        // 输入数组元素
        for (int i = 0; i < size; i++) {
            weightArray[i] = scanner.nextInt();
        }
        // 调用结果计算方法并打印结果
        System.out.println(determineResult(size, weightArray));
    }

    /**
     * 判断数组是否可以划分为 XOR 和为 0 的部分
     *
     * @param size 数组大小
     * @param weightArray 输入数组
     * @return 如果可以划分，返回总和减去最小值；否则返回 "NO"
     */
    public static String determineResult(int size, int[] weightArray) {
        // 对数组进行排序
        Arrays.sort(weightArray);

        // 最小值
        int smallest = weightArray[0];
        // 总和初始化为最小值
        int correctTotal = smallest;
        // XOR 和初始化为最小值
        int xorSum = smallest;

        // 遍历剩余的元素，计算总和和 XOR 和
        for (int i = 1; i < size; i++) {
            correctTotal += weightArray[i]; // 累加当前元素
            xorSum ^= weightArray[i];      // 计算 XOR 和
        }

        // 如果 XOR 和为 0，返回总和减去最小值；否则返回 "NO"
        return xorSum == 0 ? String.valueOf(correctTotal - smallest) : "NO";
    }
}

C++解法

解题思路

问题描述：

给定一个整数数组 weights，判断是否可以将其划分为若干子数组，使得这些子数组的 XOR 和为 0。
如果可以，返回总和减去数组中的最小值；如果不可以，返回 “NO”。
解法步骤：

计算 XOR 和：
遍历数组，计算其整体的 XOR 和。
如果 XOR 和不为 0，说明无法划分，直接输出 “NO”。
计算最大总和：
如果 XOR 和为 0，可以划分，将数组的总和减去最小值，作为输出结果。
数学依据：

如果一个数组的 XOR 和为 0，可以通过适当划分，使得子数组的 XOR 和也为 0。
输出总和减去最小值是基于一种贪心思想，假设通过划分后可以最大化剩余部分的和。
算法复杂度：

时间复杂度：
计算 XOR 和：O(n)。
计算总和：O(n)。
找到最小值：O(n)。
总复杂度为 O(n)。
空间复杂度：O(1)，只使用常量额外空间。

#include <iostream>
#include <vector>
#include <numeric> // 用于 std::accumulate
#include <algorithm> // 用于 std::min_element

int main() {
    int n;
    std::cin >> n; // 读取数组长度
    std::vector<int> weights(n);

    // 读取数组元素
    for (int &weight : weights) {
        std::cin >> weight;
    }

    // 计算整个数组的 XOR 和
    int xorTotal = 0;
    for (int weight : weights) {
        xorTotal ^= weight;
    }

    // 如果 XOR 和不为 0，无法划分为 XOR 和为 0 的部分
    if (xorTotal != 0) {
        std::cout << "NO" << std::endl;
        return 0;
    }

    // 计算数组总和并减去最小值
    int maxWeight = std::accumulate(weights.begin(), weights.end(), 0) - *std::min_element(weights.begin(), weights.end());
    
    // 输出结果
    std::cout << maxWeight << std::endl;

    return 0;
}