当前位置：首页 > news >正文

【OD】【E卷】【真题】【100分】分苹果（PythonJavaJavaScriptC++C）

news 2024/10/22 9:31:42

题目描述

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

输出

示例2

输入

8
7258 6579 2602 6716 3050 3564 5396 1773

输出

解题思路

这道题目要求你在给定的条件下计算A和B两个人分苹果的结果。A的要求是按照二进制加法（不进位）等分苹果，而B希望在满足A的要求下获取苹果总重量的最大值。如果无法满足A的要求，则输出-1。

题目分析

二进制加法不进位：
- 二进制加法不进位的意思是直接对每一位进行相加，但不进行进位处理。
- 比如：12（1100）和5（0101）相加的结果是9（1001），因为在二进制表示中：
  - 1+0 = 1
  - 1+1 = 0（不进位）
  - 0+0 = 0
  - 0+1 = 1
题目要求：
- 你需要找到一个办法，把苹果分成两堆，使得两堆苹果的总重量按二进制加法（不进位）结果相等。
- 在满足这个条件的前提下，让B获取的苹果总重量最大。

示例分析

示例 1

输入：
```
3
3 5 6
```
分析：
- 可能的分法有：
  - 3, 5 | 6
  - 3, 6 | 5
  - 5, 6 | 3
- 根据二进制加法规则（不进位），3 + 5 = 6，3 + 6 = 5，5 + 6 = 3。
- 通过手动验证，发现其中一堆可以是{5, 6}，另一堆是{3}，此时B获取的总重量最大为11。

示例 2：

8
7258 6579 2602 6716 3050 3564 5396 1773

计算总异或和：
首先计算所有苹果重量的异或和。如果总异或和不为 0，那么就不可能按照 A 的规则将苹果分成两堆，此时输出 -1。
XOR sum = 7258 ⊕ 6579 ⊕ 2602 ⊕ 6716 ⊕ 3050 ⊕ 3564 ⊕ 5396 ⊕ 1773 \text{XOR sum} = 7258 \oplus 6579 \oplus 2602 \oplus 6716 \oplus 3050 \oplus 3564 \oplus 5396 \oplus 1773 XOR sum=7258⊕6579⊕2602⊕6716⊕3050⊕3564⊕5396⊕1773

通过逐个异或，可以计算出：

XOR sum = 0 \text{XOR sum} = 0 XOR sum=0

因为总异或和为 0，所以有可能按照 A 的规则分堆。
找出 B 的最大重量：
因为 XOR 总和为 0，我们可以找到一种分法，使得两个堆的异或结果为 0。我们将总重量计算出来：

Total Sum = 7258 + 6579 + 2602 + 6716 + 3050 + 3564 + 5396 + 1773 = 36838 \text{Total Sum} = 7258 + 6579 + 2602 + 6716 + 3050 + 3564 + 5396 + 1773 = 36838 Total Sum=7258+6579+2602+6716+3050+3564+5396+1773=36838
然后我们考虑两堆的分配，使得其中一个堆的重量最大。因为总异或和为 0，我们可以选择总重量中最小的那个数，从总和中减去，这样可以最大化 B 的重量：

Minimum Weight = min ⁡ ( 7258 , 6579 , 2602 , 6716 , 3050 , 3564 , 5396 , 1773 ) = 1773 \text{Minimum Weight} = \min(7258, 6579, 2602, 6716, 3050, 3564, 5396, 1773) = 1773 Minimum Weight=min(7258,6579,2602,6716,3050,3564,5396,1773)=1773

因此，B 可以获得的最大重量是：

Max Weight for B = Total Sum − Minimum Weight = 36838 − 1773 = 35165 \text{Max Weight for B} = \text{Total Sum} - \text{Minimum Weight} = 36838 - 1773 = 35165 Max Weight for B=Total Sum−Minimum Weight=36838−1773=35165
输出结果：

最终，输出 B 可以获取的最大苹果重量：

结论

如果总异或和为 0，找到最小的重量，将其分给 A，B 的最大重量是总和减去这个最小重量。
如果总异或和不为 0，则输出 -1。

Java

import java.util.Scanner;public class Main {public static void main(String[] args) {// 创建一个扫描器对象，用于读取输入Scanner scanner = new Scanner(System.in);// 读取苹果的数量 nint n = scanner.nextInt();// 创建一个大小为 n 的数组，用于存储每个苹果的重量int[] a = new int[n];// 循环读取每个苹果的重量，并存储到数组中for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();}// 初始化异或总和变量int sums = 0;// 初始化最小值变量为整型的最大值int min = Integer.MAX_VALUE;// 遍历所有苹果的重量for (int x : a) {// 按位异或操作，更新异或总和sums = sums ^ x;// 找到当前最小的苹果重量if (x < min) {min = x;}}// 如果异或总和不为 0，则无法按 A 的规则分堆，输出 -1if (sums != 0) {System.out.println(-1);} else {// 计算所有苹果重量的总和int sum = 0;for (int x : a) {sum += x;}// 输出 B 可以获取的最大苹果重量（总和减去最小的苹果重量）System.out.println(sum - min);}}
}

Python

import sys# 读取苹果的数量 n
n = int(input())
# 读取每个苹果的重量并存储到列表 a 中
a = list(map(int, input().split()))# 初始化异或总和
sums = 0
# 初始化最小值为系统的最大整数
min_val = sys.maxsize
# 遍历所有苹果的重量
for x in a:# 按位异或操作，更新异或总和sums = sums ^ x# 找到当前最小的苹果重量if x < min_val:min_val = x# 如果异或总和不为 0，则无法按 A 的规则分堆，输出 -1
if sums != 0:print(-1)
else:# 计算所有苹果重量的总和total_sum = sum(a)# 输出 B 可以获取的最大苹果重量（总和减去最小的苹果重量）print(total_sum - min_val)

JavaScript

const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout
});let n;  // 苹果数量
let a;  // 每个苹果的重量数组// 读取输入的第一行，苹果数量 n
rl.on('line', (inputN) => {n = parseInt(inputN);// 读取输入的第二行，苹果的重量列表rl.on('line', (inputA) => {a = inputA.split(' ').map(Number);// 初始化异或总和let sums = 0;// 初始化最小值为 JavaScript 中安全的最大整数let min_val = Number.MAX_SAFE_INTEGER;// 遍历所有苹果的重量a.forEach((x) => {// 按位异或操作，更新异或总和sums = sums ^ x;// 找到当前最小的苹果重量if (x < min_val) {min_val = x;}});// 如果异或总和不为 0，则无法按 A 的规则分堆，输出 -1if (sums !== 0) {console.log(-1);} else {// 计算所有苹果重量的总和const total_sum = a.reduce((sum, x) => sum + x, 0);// 输出 B 可以获取的最大苹果重量（总和减去最小的苹果重量）console.log(total_sum - min_val);}rl.close();  // 关闭读取接口});
});

C++

#include <iostream>
#include <vector>
#include <limits>int main() {int n;// 读取苹果的数量 nstd::cin >> n;// 创建一个大小为 n 的向量，用于存储每个苹果的重量std::vector<int> a(n);// 循环读取每个苹果的重量，并存储到向量中for (int i = 0; i < n; i++) {std::cin >> a[i];}// 初始化异或总和变量int sums = 0;// 初始化最小值变量为整型的最大值int min = std::numeric_limits<int>::max();// 遍历所有苹果的重量for (int x : a) {// 按位异或操作，更新异或总和sums = sums ^ x;// 找到当前最小的苹果重量if (x < min) {min = x;}}// 如果异或总和不为 0，则无法按 A 的规则分堆，输出 -1if (sums != 0) {std::cout << -1 << std::endl;} else {// 计算所有苹果重量的总和int sum = 0;for (int x : a) {sum += x;}// 输出 B 可以获取的最大苹果重量（总和减去最小的苹果重量）std::cout << sum - min << std::endl;}return 0;
}

C语言

#include <stdio.h>
#include <limits.h>  // 用于定义整型的最大值 INT_MAXint main() {int n;// 读取苹果的数量 nscanf("%d", &n);// 创建一个大小为 n 的数组，用于存储每个苹果的重量int a[n];// 循环读取每个苹果的重量，并存储到数组中for (int i = 0; i < n; i++) {scanf("%d", &a[i]);}// 初始化异或总和变量int sums = 0;// 初始化最小值变量为整型的最大值int min = INT_MAX;// 遍历所有苹果的重量for (int i = 0; i < n; i++) {// 按位异或操作，更新异或总和sums = sums ^ a[i];// 找到当前最小的苹果重量if (a[i] < min) {min = a[i];}}// 如果异或总和不为 0，则无法按 A 的规则分堆，输出 -1if (sums != 0) {printf("-1\n");} else {// 计算所有苹果重量的总和int sum = 0;for (int i = 0; i < n; i++) {sum += a[i];}// 输出 B 可以获取的最大苹果重量（总和减去最小的苹果重量）printf("%d\n", sum - min);}return 0;
}