题目重点：从高位到低位试掩码，以每个数满足掩码的最小增量及 M 个最低成本判断可行。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 整数非负、允许任意分配加法预算、选择恰好m个不同位置；无需连续。
- 不允许减值，预算可不花完；固定宽度环境另定溢出界。
解题路线
- 可行掩码t表示存在m项最终数都包含t的每个1位，即(y&t)==t；它不要求最终数恰等于t，也不要求AND恰等于t。
- 对原值a，找t中a缺少的最高位b。若无缺位，cost=0。否则保留a在b之上的前缀，把b置1，再让低位恰为t所需低位；这给最小满足条件且≥a的y。
- 为什么最小：保持高前缀时b必须从0变1，因此低位可以清零再填必要位；若改变更高前缀使值更大，必不优于该构造。用加法可能清除低位，所以不能直接把(a|t)-a当所有情况的最小成本。
- 计算所有项cost，选m个最小值的和；彼此增量独立，因此这个和≤预算当且仅当该掩码可行。选择过程可改变，不锁定前一次选中的m项。
- 高位优先试answer|2^b，可行就保留，否则放弃。可行性对删除1位封闭，任意更高首差位优先于全部低位和，故逐位得到最大整数AND。最高可能位用max(a)+budget界定。
手动走一遍
题目输入[5,4,1,7,2]、m=3、budget=3可将4和5增至6，选原值4、5、7得到6&6&7=6，花3；作者写“选4,5,6”中的6不在输入，本文明确修正。另a=3,t=4最小y=4仅花1，OR得到7花4会错。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def increment_cost(value, mask):
"""Smallest y >= value such that y & mask == mask, minus value."""
missing = mask & ~value
if not missing:
return 0
bit = missing.bit_length()-1
lower = (1 << bit)-1
target = (value >> (bit+1) << (bit+1)) + (1 << bit) + (mask & lower)
return target-value
def maximize_and(values, selected_count, budget):
if not 1 <= selected_count <= len(values) or budget < 0 or any(v < 0 for v in values):
raise ValueError("invalid nonnegative input or selection size")
answer = 0
for bit in range((max(values)+budget).bit_length()-1,-1,-1):
candidate = answer | (1 << bit)
costs = sorted(increment_cost(v,candidate) for v in values)
if sum(costs[:selected_count]) <= budget:
answer = candidate
return answer
复杂度
B个有效位，排序版本O(B·n log n)次有界整数工作、O(n)临时空间；Python大整数bit_length/位操作有位成本。选m最小可用heap/selection优化，但不能省略逐项可行成本。
易错点与追问
容易失分的边界
- 用a|mask直接求最小加法成本。
- 锁定固定m项后逐位加，错过更优子集。
- 试位时忽略已保留高位。
- 抄题目不存在的输入6。
继续深挖
- 返回最终选择与加法分配怎么重建？
- m=n能否省排序？
- 允许减法时该最小成本公式为何失效？
