题目详解：2021A - Meaning Mean（平均值的意义）

问题重述

我们有一个长度为 $n$ 的正整数数组 $a$。每次操作：

• 选择两个不同位置的数 $a_i$ 和 $a_j$
• 删除它们，并加入 $\left\lfloor \frac{a_i + a_j}{2} \right\rfloor$
• 重复直到只剩一个数

目标是最大化最后剩下的那个数。

---

核心思路

第一步：忽略向下取整，先考虑精确平均值

假设我们暂时忽略 $\lfloor \cdot \rfloor$，那么一次操作就是把两个数变成它们的算术平均： [ \frac{a_i + a_j}{2} ]

这是一个线性操作。我们可以把整个过程看作：每个原始数字最终对结果有一个贡献系数，并且这些系数的和必须为 $1$。

为什么系数和为 $1$？

• 初始有 $n$ 个数，每个数“携带”自己的值。
• 每次操作：删除两个数，加入它们的平均值。这相当于把这两个数的“权重”平均分配给新数。
• 最终只剩一个数，它包含了所有原始数的信息，且权重总和为 $1$。

因此，最终结果可以写成： [ x = \sum_{k=1}^n c_k \cdot a_k ] 其中 $c_k \ge 0$，且 $\sum c_k = 1$。

---

第二步：系数的可能分布

通过一些例子可以发现：

• 如果按顺序合并 $a_1, a_2$，再与 $a_3$ 合并，等等，那么最后：
  • $a_n$ 的系数是 $\frac{1}{2}$
  • $a_{n-1}$ 的系数是 $\frac{1}{4}$
  • $a_{n-2}$ 的系数是 $\frac{1}{8}$
  • ...
  • $a_1$ 的系数是 $\frac{1}{2^{n-1}}$

检查一下： [ \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2^{n-1}} = 1 - \frac{1}{2^{n-1}} < 1 ] 等等，这里不对劲！因为 $a_1$ 的系数其实是 $\frac{1}{2^{n-1}}$，但总和确实小于 $1$。

实际上，我们还需要加上最后一次合并时来自前面的贡献。更准确地说：
最终结果是： [ x = \frac{a_n}{2} + \frac{a_{n-1}}{4} + \frac{a_{n-2}}{8} + \dots + \frac{a_1}{2^{n-1}} + \frac{\text{某个常数}}{2^{n-1}}? ] 其实每次合并都会产生一个“残余项”，但最终可以证明：
如果我们按升序排序后从最小的开始合并，那么最大的数得到最大的系数。

---

第三步：最优策略

为了最大化 $\sum c_k a_k$，在 $\sum c_k = 1$ 的约束下，应该把最大的系数分配给最大的 $a_k$。

系数的大小由合并顺序决定：

• 越晚参与合并的数，被平均的次数越少，系数越大。
• 实际上，最优策略是：
  1. 将数组升序排序
  2. 从最小的两个开始合并
  3. 将结果与下一个最小的合并
  4. 依此类推

这样，最大的数 $a_n$ 只参与最后一次合并，系数为 $\frac{1}{2}$；
次大的数 $a_{n-1}$ 参与倒数第二次合并，系数为 $\frac{1}{4}$；
以此类推。

---

第四步：为什么带向下取整也一样有效？

因为所有操作都是除以 $2$ 并向下取整，所以：

• 如果我们在精确平均值下得到最大值，那么带向下取整的结果只会更小或相等。
• 但通过上述顺序合并，我们可以尽可能保留大数的精度，使向下取整的损失最小。
• 实际上可以证明：这个贪心顺序在原始问题中也是最优的。

---

第五步：算法实现

对于每个测试用例：

1. 将数组 $a$ 升序排序
2. 初始化 ans = a[0]
3. 从 $i = 1$ 到 $n-1$： [ ans = \left\lfloor \frac{ans + a[i]}{2} \right\rfloor ]
4. 输出 ans

时间复杂度：$O(n \log n)$（排序）

---

第六步：验证样例

样例1：$[1,7,8,4,5]$

排序后：$[1,4,5,7,8]$

• 第一步：$\lfloor (1+4)/2 \rfloor = \lfloor 2.5 \rfloor = 2$
• 第二步：$\lfloor (2+5)/2 \rfloor = \lfloor 3.5 \rfloor = 3$
• 第三步：$\lfloor (3+7)/2 \rfloor = \lfloor 5 \rfloor = 5$
• 第四步：$\lfloor (5+8)/2 \rfloor = \lfloor 6.5 \rfloor = 6$ ✅

样例2：$[2,6,5]$

排序：$[2,5,6]$

• 第一步：$\lfloor (2+5)/2 \rfloor = \lfloor 3.5 \rfloor = 3$
• 第二步：$\lfloor (3+6)/2 \rfloor = \lfloor 4.5 \rfloor = 4$ ✅

样例3：$[5,5,5,5,5]$

排序后全是 $5$

• 每次合并：$\lfloor (5+5)/2 \rfloor = 5$
• 最终：$5$ ✅

---

总结

• 问题本质：在每次取两个数的平均值（向下取整）的操作下，最大化最终结果。
• 关键观察：最终结果是原始数的加权平均，权重和为 $1$。
• 最优策略：升序排序后，从最小的开始依次合并，这样最大的数获得最大权重。
• 复杂度：$O(n \log n)$，完全满足 $n \le 50$ 的限制。