南平建设集团网站,网站首页设计风格,网站的类别,做康复医院网站目录
题目部分
解读与分析
代码实现 题目部分
题目分积木难度难题目说明Solo和koko是两兄弟#xff0c;妈妈给了他们一大堆积木#xff0c;每块积木上都有自己的重量。现在他们想要将这些积木分成两堆。哥哥Solo负责分配#xff0c;弟弟koko要求两个人获得的积木总重量“…目录
题目部分
解读与分析
代码实现 题目部分
题目分积木难度难题目说明Solo和koko是两兄弟妈妈给了他们一大堆积木每块积木上都有自己的重量。现在他们想要将这些积木分成两堆。哥哥Solo负责分配弟弟koko要求两个人获得的积木总重量“相等”根据Koko的逻辑个数可以不同不然就会哭但koko只会先将两个数转成二进制再进行加法而且总会忘记进位每个进位都忘记。如当2511101加111011时koko得到的计算结果是1810010 11001 01011 ------------- 10010 Solo想要尽可能使自己得到的积木总重量最大且不让koko哭。输入描述3 3 5 6 第一行是一个整数N( 2≤ N ≤100 )表示有多少块积木第二行为空格分开的N个整数Ci(1 ≤ Ci ≤)表示第i块积木的重量。输出描述11 让koko不哭输出Solo所能获得积木的最大总重量否则输出“-1”。补充说明如果能让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);}
} (完)
