分苹果
题目描述:
A、B两个人把苹果分为两堆,
A希望按照他的计算规则等分苹果,他的计算规则是按照二进制加法计算,并且不计算进位 12+5=9(1100 + 0101 = 9),
B的计算规则是十进制加法,包括正常进位,B希望在满足A的情况下获取苹果重量最多。
输入苹果的数量和每个苹果重量,输出满足A的情况下B获取的苹果总重量。
如果无法满足A的要求,输出-1。
数据范围:
1 <= 总苹果数量 <= 20000
1 <= 每个苹果重量 <= 10000
输入输出描述:
输入描述:
输入第一行是苹果数量:3
输入第二行是每个苹果重量:3 5 6
输出描述:
输出第一行是B获取的苹果总重量:11
示例1:
输入:
3
3 5 6
输出:
11
示例2:
输入:
8
7258 6579 2602 6716 3050 3564 5396 1773
输出:
35165
解题思路:
1:明确不进位的二进制加法,即异或操作
2:A按照二进制加法计算,且要求等分:是否能等分,取决于所有苹果的重量做异或运算后结果是否为0
。
比如:12 + 5 = 9≠0(1100 + 0101 = 9),故当苹果为:12、5时,不能按照A的要求等分。
比如:12 + 5 + 9 = 0(1100 + 0101 + 1001 = 0),故当苹果为:12、5、9时,可以能按照A的要求等分。此时可以分为:A-5,B-21
故解题思路为:计算出所有苹果的异或结果,同时记录下最轻的苹果重量min:
①:如果异或结果为0,说明可以按照A的规则分,A分到最轻的苹果,剩余苹果都归B。
(异或运算的结合律:(a ^ b) ^ c = a ^ (b ^ c))
②:如果异或结果不为0,说明不可以按照A的规则均分,输出-1。
异或操作:
异或运算,也称为“异或操作”或“异或运算符”,是一种逻辑运算,用于比较两个值的位(二进制位)是否不同。异或运算的结果为1表示对应的位不同,结果为0表示对应的位相同
。
异或运算的符号通常用“^”表示,例如:
0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
异或运算还具有一些重要的性质:
交换律:a ^ b = b ^ a
结合律:(a ^ b) ^ c = a ^ (b ^ c)
自反性:a ^ a = 0
零值性:a ^ 0 = a
幂等性:a ^ b ^ b = a
逆运算:对于任意固定的数 b,a ^ b ^ b = a
在计算机编程中,异或运算的应用非常广泛,例如:
交换两个变量的值,无需使用临时变量:a = a ^ b; b = a ^ b; a = a ^ b;
判断奇偶性:一个数与1进行异或操作,结果为1表示奇数,结果为0表示偶数。
用于加密和校验算法,如校验和、CRC(循环冗余校验)等。
异或运算只关注对应位的值是否不同,而不关心具体的数值。
代码:
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = Integer.parseInt(scanner.nextLine());
int[] weights = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int aw = 0;
int bw = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
// 不进位的二进制加法,即:做异或操作
aw ^= weights[i];
bw += weights[i];
min = Math.min(weights[i], min);
}
if (aw == 0) {
System.out.println(bw - min);
} else {
System.out.println(-1);
}
}