目录

题目部分

解读与分析

代码实现

题目部分

3
3 5 6
第一行是一个整数N( 2≤ N ≤100 )，表示有多少块积木；第二行为空格分开的N个整数Ci(1 ≤ Ci ≤)，表示第i块积木的重量。

解读与分析

题目解读：

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

(完)