华为OD机考算法题：分积木

题目部分


题目	分积木
难度	难
题目说明	Solo和koko是两兄弟，妈妈给了他们一大堆积木，每块积木上都有自己的重量。现在他们想要将这些积木分成两堆。哥哥Solo负责分配，弟弟koko要求两个人获得的积木总重量“相等”（根据Koko的逻辑），个数可以不同，不然就会哭，但koko只会先将两个数转成二进制再进行加法，而且总会忘记进位（每个进位都忘记）。如当25（11101）加11（1011）时，koko得到的计算结果是18（10010）： 11001 + 01011 ------------- 10010 Solo想要尽可能使自己得到的积木总重量最大，且不让koko哭。
输入描述	3 3 5 6 第一行是一个整数N( 2≤ N ≤100 )，表示有多少块积木；第二行为空格分开的N个整数Ci(1 ≤ Ci ≤ $10^{6}$ )，表示第i块积木的重量。
输出描述	11 让koko不哭，输出Solo所能获得积木的最大总重量；否则输出“NO”。
补充说明	如果能让koko不哭，输出Solo所能获得的积木的总重量，否则输出-1。该样例输出为 11 。解释：Solo 能获得重量为 5 和 6 的两块积木，5 转换成二进制是 101， 6 的二进制是 110，按照 kolo 的计算方法（忘记进位），结果为 3（二进制 011）。kolo 获得重量为 3 的积木，而 solo 获得重量为 11（十进制，5 + 6）的积木。
------------------------------------------------------
示例
示例1
输入	3
输出	3 5 6
说明	11

解读与分析

题目解读：

此题要求从一堆数字中，把它们分成 2 份，按照加法不进位的方式，使这两份之和“相等”。在“相等”的前提下，输出实际总和较大的那个数字。
如果任何分法都不能保证“相等”，则输出 -1。

分析与思路：

做加法不进位，0 + 0 = 0， 0 + 1 = 1， 1 + 1 = 0。实际上，这就是数字异或（XOR）。

原题中，要求按照异或的方式分成两“等份”，那这两等分异或之后，最终的结果为 0。由于异或的结果与顺序无关，即这一堆数字无论怎么改变顺序，最后异或的结果一定是 0 。既然要求两份中其中一份的数字最大，可以把最小的数字作为一份，其他所有的数字作为一份。最终所有数字之和减去最小的数字，即为输出结果。

如果所有数字的异或结果不为 0，则输出 -1。

那我们的思路就变得很简单了，申明 3 个变量：
1. xorValue，整形数字，初始值为0，记录所有数字的异或值。
2. sum，整形数字，初始值为0，记录所有数字之和。
3. minValue，整形数字，初始值为整形数字的最大值，记录所有数字中的最小值。

遍历所有的数字（设当前正在遍历的数字为 curValue），进行如下操作：
1. 把 xorValue 与 curValue 异或，把结果赋值给 xorValue；
2. 把 curValue 的值加到 sum中；
3. 判断 curValue 与 minValue 的大小，如果 curValue 更小，把它赋值给 minValue。
遍历完所有数字后，如果：
· xorValue 不等于 0 ，输出 -1。
· xorValue 等于 0，输出 ( sum - minValue )。

此题只需要遍历一次数字，使用了 3 个整形变量，时间复杂度为 O(n)，空间复杂度为 O(1)。

代码实现

Java代码

import java.util.Scanner;

/**
 * 分积木
 * @since 2023.09.14
 * @version 0.1
 * @author Frank
 *
 */
public class BlockDivision {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String input = sc.nextLine();
			int count = Integer.parseInt( input );
			input = sc.nextLine();
			String[] numbers = input.split( " " );
			// 此处 count == numbers.count，可以完全不用考虑 count.
			processBlockDivision( numbers );
		}
	}

	private static void processBlockDivision( String numbers[] )
	{
		int xorValue = 0;
		int sum = 0;
		int minValue = Integer.MAX_VALUE;
		for( int i = 0; i < numbers.length; i ++ )
		{
			int curValue = Integer.parseInt( numbers[i] );
			xorValue ^= curValue;
			sum += curValue;
			if( curValue < minValue )
			{
				minValue = curValue;
			}
		}
		if( xorValue != 0 )
		{
			System.out.println( -1 );
		}else
		{
			System.out.println( sum - minValue );
		}
	}
	
}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {
    while (line = await readline()) {
        // count 可以忽略
        var count = parseInt(line);
        line = await readline();
        var numberArr = line.split(" ");
        processBlockDivision(numberArr);
    }
}();

function processBlockDivision( numbers ) {
    var xorValue = 0;
    var sum = 0;
    var minValue = Number.MAX_VALUE;
    for (var i = 0; i < numbers.length; i++) {
        var curValue = parseInt(numbers[i]);
        xorValue ^= curValue;
        sum += curValue;
        if (curValue < minValue) {
            minValue = curValue;
        }
    }
    if (xorValue != 0) {
        console.log(-1);
    } else {
        console.log(sum - minValue);
    }
}

(完)