P4000. 分苹果

解题思路

题干阅读理解

本题的题意非常费解，说人话就是：

• 把数组 apples 分成两个部分 apples1 和 apples2，分别作为 A 和 B 获得的苹果数。
• 分别对 apples1 和 apples2 求异或和，得到 xorsum1 和 xorsum2。
• xorsum1 和 xorsum2 需要满足两者相等（即所谓的按照 A 的方法进行苹果平分）。
• 对 apples1 和 apples2 分别进行十进制求和，得到 apples1_sum 和 apples2_sum。
• 要求找到一种分苹果的方法，使得 `apples2_sum` 最大，作为 B 获得的苹果数。

如何满足 A 的分配规则

对于给定的任意一个数组 apples，我们需要思考数组本身满足什么条件时，A 的分配规则会得到满足。

由上一步的分析得知，如果 A 的分配规则满足，那么 apples 可以被分成 apples1 和 apples2 两部分，这两部分的异或和 xorsum1 和 xorsum2 满足两者相等的条件：

根据异或操作的性质，很容易得到：

如果把 xorsum1 和 xorsum2 分别展开并使用异或操作交换律，由于 apples1 和 apples2 正好组成了 apples，我们可以得到：

上式的左边部分其实是 apples 数组的异或和。

换句话说，如果 `apples` 数组的异或和为 0，那么 `apples` 数组一定可以拆成 `apples1` 和 `apples2` 两部分，满足 A 的分配规则。进一步地，无论 apples 拆成怎么样的两部分，都能够满足 A 的分配规则。

所以判断 A 的分配规则是否能满足的依据非常简单，即判断 `apples` 的异或和是否等于 0。

如何贪心地让 B 获利

如果上述步骤想明白了，剩下的操作实际上非常简单了。由于无论 apples 拆成怎么样的两部分，都能够满足 A 的分配规则，为了让 B 尽可能多地获得苹果，我们只需要贪心地让 A 获得的那一部分 `apples1` 在十进制的数值上尽可能地小即可。A 取最小的结果即为 min(apples)，此时 B 获得的苹果数量为 sum(apples) - min(apples)，即为答案。

上述核心思路整理成代码，实际上非常简短：

复杂度分析 设 n 为苹果的数量。整段代码只做了几件线性工作：先一次遍历求全体重量的异或和 xorsum，为 O(n)；当 xorsum 等于 0 时，再求 sum(nums) 与 min(nums)（C++ 版在同一个循环里同时求和与求最小值），也是一次 O(n) 扫描。没有排序、没有嵌套循环，因此总时间复杂度为 O(n)，瓶颈就是这两趟遍历。空间上，除了存放输入的数组本身，只用到 xorsum、总和、最小值这几个标量变量，辅助空间为 O(1)。