刷题笔记合集🔗

分积木

问题描述

Solo和koko是两兄弟，妈妈给了他们一大堆积木，每块积木上都有自己的重量。现在他们想要将这些积木分成两堆。哥哥Solo负责分配，弟弟koko要求两个人获得的积木总重量"相等"（根据Koko的逻辑），个数可以不同，不然就会哭，但koko只会先将两个数转成二进制再进行加法，而且总会忘记进位（每个进位都忘记）。如当25（11001）加11（01011）时，koko得到的计算结果是18（10010）：

 11001
+01011
--------
 10010

Solo想要尽可能使自己得到的积木总重量最大，且不让koko哭。

输入格式

第一行是一个整数 ，表示有多少块积木。

第二行为空格分开的 个整数 ，表示第 块积木的重量。

输出格式

如果能让koko不哭，输出Solo所能获得积木的最大总重量；否则输出"NO"。

样例输入

3
3 5 6

样例输出

11

数据范围

题解

这道题的关键在于理解Koko的计算逻辑。仔细分析题目，可以发现Koko的计算方式其实就是二进制的"异或"运算（XOR）。

当我们要判断能否让Koko不哭，实际上是在问：能否将所有积木分成两堆，使得两堆积木的重量在Koko的计算逻辑下相等？

对于异或运算，如果两个相同的数进行异或，结果是0。所以，如果我们想要两堆积木在Koko的逻辑下"重量相等"，那么这两堆积木的异或和必须相等，也就是说，所有积木的异或和必须是0。

解题思路如下：

1. 计算所有积木重量的异或和
2. 如果异或和为0，说明可以平分（按照Koko的逻辑）
3. 为了让Solo获得的重量最大，应该给Koko分配最小重量的积木，其余都给Solo

具体实现时：

1. 对积木按重量排序
2. 取出最轻的积木，记为min
3. 计算所有积木的异或和，如果为0，表示可以平分
4. 如果可以平分，Solo应该拿走除了最轻积木外的所有积木，总重量就是所有积木重量之和减去min

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

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()
n = int(input())
w = list(map(int, input().split()))

# 计算积木能否按Koko的逻辑等分
def solve(weights):
    # 排序找出最小值
    weights.sort()
    min_w = weights[0]
    
    # 计算实际总和和Koko逻辑下的和
    real_sum = min_w  # 实际总和
    xor_sum = min_w   # Koko逻辑下的和（异或和）
    
    # 处理剩余积木
    for i in range(1, len(weights)):
        val = weights[i]
        real_sum += val  # 累加实际重量
        xor_sum ^=