刷题笔记合集🔗

分苹果

问题描述

A、B两个人把苹果分为两堆，A希望按照他的计算规则等分苹果，他的计算规则是按照二进制加法计算，并且不计算进位 12+5=9（1100 + 0101 = 9），B的计算规则是十进制加法，包括正常进位，B希望在满足A的情况下获取苹果重量最多。

输入苹果的数量和每个苹果重量，输出满足A的情况下B获取的苹果总重量。

如果无法满足A的要求，输出-1。

输入格式

第一行是一个整数 ，表示苹果的数量。

第二行是 个空格分隔的整数，表示每个苹果的重量。

输出格式

输出一个整数，表示B能获取的最大苹果总重量。如果无法满足A的要求，输出-1。

样例输入

3
3 5 6

8
7258 6579 2602 6716 3050 3564 5396 1773

样例输出

11

35165

数据范围

• （总苹果数量）
• （每个苹果重量）

题解

这道题的核心是理解A的计算规则。当我们仔细分析时，发现A的"不计算进位的二进制加法"实际上就是异或运算（XOR）。

问题可以转化为：将所有苹果分成两组，使得两组苹果的异或和相等，并且B组的普通加法和尽可能大。

为了实现这个目标，我们可以这样思考：

1. 如果所有苹果的异或和为0，那么把所有苹果都给B是最优的
2. 如果所有苹果的异或和不为0，那么无法满足A的要求，输出-1
3. 如果所有苹果的异或和为0，但我们还需要至少给A一个苹果，那么应该给A重量最小的那个苹果

具体算法步骤：

1. 计算所有苹果重量的异或和
2. 如果异或和为0，说明可以平分（按照A的计算规则）
3. 给A分配重量最小的苹果，其余全部给B
4. 输出B获得的总重量

时间复杂度为O(n log n)，主要消耗在排序上，对于给定的数据范围（n≤20000），这个复杂度是可以接受的。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 读取输入
n = int(input())
weights = list(map(int, input().split()))

def solve(apples):
    # 按重量排序
    apples.sort()
    
    # 最小重量
    min_w = apples[0]
    
    # 计算异或和
    xor_sum = min_w
    # 计算实际总和
    total = min_w
    
    # 处理剩余苹果
    for i in range(1, len(apples)):
        w = apples[i]
        xor_sum ^= w  # 异或运算
        total += w    # 普通加法
    
    # 判断是否可以满足A的要求
    if xor_sum == 0:
        # 可以满足，B拿走除最轻以外的所有苹果