1000ms

Difficulty: 6

所属公司 : 美团

时间 :2025年8月16日-算法岗

算法与标签>位运算

会员或题库专享

请先，开通会员或购买题库美团机考编程题库，可解锁完整内容。

购买美团机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（美团机考编程题库），可解锁完整内容。

购买题库开通会员

题解

结论
- 设数组为 $a_1,\dots,a_n$ ，最大值为 $M=\max(a_i)$ ，其二进制长度为 $L$ （特别地，当 $M=0$ 时 $L=1$ ）。
- 记按位与为 $A=\bigwedge_{i=1}^n a_i$ ，定义掩码 $mask=2^L-1$ 。
- 使总和最大的最小初始 $x$ 为：

题目内容

一位研究员有 $n$ 个实验样本，每个样本含有一个非负整数的能量值。他还有一个能量转换装置，可以设定一个非负整数作为初始能量。装置能量的二进制表示的位数不能超过所有样本初始能量中最大值的二进制位数（特别地，能量值 $0$ 的位数为 $1$ ）。

研究员可以重复进行以下操作：

选择一个样本，记其当前能量为 $E$ ，装置当前能量为 $X$ 。
同时将样本能量更新为 $E$ 与 $X$ 的「融合」，将装置能量更新为 $E$ 与 $X$ 的「萃取」。

定义两种位运算（均对二进制表示的每一位独立操作）：

融合：若某一位上两个数中至少有一个为 $1$ ，则结果该位为 $1$ ，否则为 $0$ 。