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

目录

题目部分

解读与分析

代码实现

---

题目部分

---

解读与分析

题目解读：

此题要求从一堆数字中，把它们分成 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);
    }
}

(完)