fgg blog

脑筋急转弯


题目描述
A 和 B 两个人要分苹果。A 希望按照他的计算规则得到平均分配的苹果,而 B 希望在满足 A 的条 件下获得尽可能多的苹果量。

A 的计算规则是按照二进制加法进行,并不计算进位。例如,12 + 5 = 9 (1100 + 0101 = 1001)。

B 的计算规则是正常的十进制加法,包括进位。

给定苹果的数量和每个苹果的重量,计算并满足 A 的要求的情况下,B 能获得的最大苹果总重量。 如果无法满足 A 的要求,则输出 -1。

输入描述
第一行包含一个整数 n,表示苹果的数量。

第二行包含 n 个整数,表示每个苹果的重量 w1, w2, …, wn。

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

示例1
输入:
3
3 5 6

输出:
11

说明:
通过二进制无进位加法,A 要求的总重量是 3 XOR 5 XOR 6 = 0,B 能获得所有的苹果,总重量为 11。

示例2
输入:
8
7258 6579 2602 6716 3050 3564 5396 1773

输出:
35165

说明:
同样按照 A 的二进制无进位规则,B 获得最大的苹果重量为 35165。


A 要求的总重量是 3 XOR 5 XOR 6 = 0,B 能获得所有的苹果,总重量为 11。

我:狗屎一样的描述,根本表述不清,甚至示例还有矛盾:A要求重量为0,B能获得所有苹果(难道 不是3个?三个苹果总重量为11吗?这又是哪门子的A的平均分配?傻A吗还是傻B?)。狗屎。2024-09-27 Fri

我:XOR1为0,则将最小值分配给A,剩下都是B的;否则输出-1。(不清楚这个狗屎做法为什么对题)。

2024-09-30 Mon:臭狗屎余臭绕鼻,三日不绝,忍无可忍还是要一探究竟是什么样的狗在胡闹,一番 搜索:

社区靓女:意思就是 平分苹果 比如例子中(三个苹果,重量分别为:3, 5, 6) 对a的算法来说:b 拿到的是5+6=3个, 剩下个3,所以 a和b 是平分的。但是对b来说 他拿到的是总重量为11的两个 苹果。所以b能拿到的,并且满足a同学要求之后的最大重量是11.

社区某靓女的解释是合题意的(此人不简单呐)。至少这个解释可以驱散多日狗屎臭味了。

进一步解析:示例告诉应试者,就去整异或运算,至于为什么,至于文字描述什么意思,至于文意互 相矛盾,那都不是事儿,想不明白可以后面去想(不要想着打一顿出题者,而是想出题者何意,去猜 猜猜)。所以,社区某靓女的解释显得极其合理(以小人心态,我简直要怀疑这人是出题者或之一), A确实想要“平均分配”苹果,但是是按照“异或”这种计算方式去“平均”,这第一步就严重挑战正常人 朴素认知里对“平均”的含义的理解。

可是“平均”在出题者的定义里,关你普通人的朴素感情什么屁事?

或许可以这样去想,作为“肉食者”一员,就要设计出这样的一种“平均分配”:5 xor 6 = 3,这样 你大A拿重量为3的苹果,我小B拿重量也为“3”的两个苹果,是够平均分配的了吧?换句话说,不管你A 拿哪个重量的苹果,最后都是平均分配。比如,我大A就是贪心,心想你个傻B,我怎么会拿3,就拿6。 小B说那没关系的哈,你看,那剩下的是重量为3和5,3 xor 5 = 6,仍然一样的哈。咱讲究的就是 一个平均分配。

有个社区靓仔说这属于是脑筋急转弯。我觉得或许这样去理解,更有幽默感吧。

转不过弯来的人,怎么气急败坏也没用,还要被嘲笑无能狂怒。门禁卡钥匙稳稳地攥在别人手里呐。

据说在六七十年代,想要整人的人都很擅长各种急转弯2。一朝权在手,便把令来行。敢不听令?

年代更久远些的一位我们的老朋友阿贵(Mr. Q),在他革命胜利的畅想中可不就是:奶奶的,从今以后,我爱谁就是谁!

代码还是附上(度狗子之腹:把它定位是简单题有错吗?3这就几行代码搞定,香不香?)

def main(arr):
    xor_sum = 0
    for a in arr:
        xor_sum ^= a
    if not xor_sum:
        return sum(arr) - min(arr)
    else:
        return -1

  1. xor是一种按位进行的运算(位运算,符号^),位运算就是基于整数的二进制表示进行的 运算。具体操作就是:只有两个对应位不同时才为1。 例子解释,$5=(101)_2, 6=(110)_2, 5 \text{^} 6=(011)_2$,$(011)_2$ 正是3的二进制表示。 ↩︎

  2. 年代久远,已不可考,也未必可信。不过王小波的《黄金时代》大约能告诉你怎么对待被人整蛊。 ↩︎

  3. 如果你恰看过LeetCode中有一道找数组中“唯一出现一次的数”的题。你甚至要觉得要是此君不 去出出高考题实为屈才。 ↩︎