题目重点：从非负内存、偶数子集与主备不等式出发，证明相邻配对最优，并处理奇数台服务器和重复容量。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 内存容量非负；可以选择一个偶数大小的子集，输入 n 本身未要求偶数。代码允许空子集，n≥2 的题目场景不受影响。
- 同一台服务器不能跨两个配对复用；相同容量的两台仍是不同服务器。
- 目标只计 primary 容量，不计 backup；不把两台内存相加当配对收益。
解题路线
- 将容量升序排序为 a。每对的收益是较小值，因此问题成为最大化所有配对的最小值总和。非负容量意味着尽可能使用 floor(n/2) 对不会变差。
- 对偶数台证明相邻配对：最大两台若分别配给更小的 x≤y，其贡献最多 x+y；改为最大两台互配、x 与 y 互配后贡献 x+次大容量，至少一样好。不断消去最大两台，得到从右侧相邻配对。
- 若 n 为奇数，任何选中的 2m 个排序值 b 都满足 b_i≤a_{i+1}：跳过最小的 a_0 后所得子集逐位置不小于任何其他子集。结合相邻配对最优，丢弃最小值即可。
- 因此从下标 n%2 开始每隔两个取一个容量求和。排序 O(n log n)，之后 O(n) 扫描；Python 整数避免累加溢出，其他语言用 64 位。
手动走一遍
训练例 memory=[1,2,3,4,9]。丢弃 1，配 (2,3)、(4,9)，primary 总和 6；把最大 9 和最小 1 配会浪费高容量 backup。偶数例 [1,2,3,4] 的收益为 1+3=4。全部相同或全部零仍适用。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def maximum_capacity(memory: list[int]) -> int:
"""Nonnegative capacities; select an even subset and pair distinct servers."""
if any(value < 0 for value in memory):
raise ValueError("memory capacities must be nonnegative")
ordered = sorted(memory)
return sum(ordered[len(ordered) % 2::2])
复杂度
O(n log n) 时间，示例 sorted 使用 O(n) 附加空间。1,093 组包含奇数及空数组的穷举对照，oracle 枚举弃用与所有配对，不依赖排序结论。
易错点与追问
容易失分的边界
- 认为 n 必须偶数，拒绝合法奇数输入。
- 把最大的半数都选为 primary，却没有为它们保留足够大的 backup。
- 按容量去重导致服务器数量改变。
- 允许负值时‘尽可能配满’证明失效，不能套用非负容量合同。
继续深挖
- 若 backup 至少是 primary 的两倍，原交换证明哪里失效？
- 若有不同机房或兼容性限制，如何建模为匹配？
- 只要求指定 m 对时，怎样选择服务器子集？
