题目题解

问题理解

给定数组 $a$，可以执行至多一次操作：选择 $i < j$，令 $a_i := a_i + a_j$，然后 $a_j := 0$。
目标是最小化前缀最小值之和：

$$S = \min(a_1) + \min(a_1, a_2) + \dots + \min(a_1, a_2, \dots, a_n). $$

---

第一步：分析前缀最小值序列

设 $m_i = \min(a_1, a_2, \dots, a_i)$。
显然 $m_1 = a_1$，且序列 $m_i$ 是非递增的（因为取最小值只会变小或不变）。

操作只会影响两个位置 $i$ 和 $j$（$i < j$）：

• $a_i$ 增加 $a_j$，可能使 $m_i$ 变大（如果 $a_i$ 原来是前缀最小值）。
• $a_j$ 变为 $0$，这会使 $m_j, m_{j+1}, \dots, m_n$ 变为 $0$（因为 $0$ 是最小值）。

因此，操作的关键作用是将 $j$ 及之后的所有前缀最小值变为 $0$。

---

第二步：不操作的情况

若不操作，则 $S = a_1 + \min(a_1, a_2) + \dots + \min(a_1, \dots, a_n)$。
由于 $a_1$ 固定，$S \ge a_1$。

---

第三步：操作的可能效果

考虑操作 $(i, j)$：

• 若 $i = 1$，则 $a_1$ 变为 $a_1 + a_j$，且 $a_j = 0$。
  此时 $m_1 = a_1 + a_j$，$m_2, \dots, m_{j-1}$ 不变（因为 $a_1$ 变大不影响它们的最小值），$m_j, \dots, m_n = 0$。
  总和变为：

  $$S = (a_1 + a_j) + \min(a_1, a_2) + \dots + \min(a_1, a_{j-1}) + 0 + \dots + 0. $$

  由于 $\min(a_1, a_k) \le a_1$（对 $k < j$），该和至少为 $a_1 + a_j$。
  实际上，可以取到 $a_1 + a_j$（当 $j=2$ 且 $a_1 \le a_2$ 时，$\min(a_1, a_2)=a_1$，总和为 $a_1+a_2$）。

• 若 $i = 2$ 且 $j = 3$（$n \ge 3$），则 $a_2$ 变为 $a_2 + a_3$，$a_3 = 0$。
  此时 $m_1 = a_1$，$m_2 = \min(a_1, a_2 + a_3)$，$m_3, \dots = 0$。
  总和为 $a_1 + \min(a_1, a_2 + a_3)$。
  若 $a_1 \le a_2 + a_3$，则和为 $2a_1$；否则为 $a_1 + a_2 + a_3$。

---

第四步：最优策略

观察可知，最优操作总是涉及最小的几个下标，因为 $0$ 会从 $j$ 开始向后传播。

经过分析（可手动验证小 $n$），最优结果总是以下两者之一：

• 不操作：$S_0 = a_1 + \min(a_1, a_2) + \dots + \min(a_1, \dots, a_n)$。
• 操作 $(1, 2)$：$S_1 = a_1 + a_2$（因为 $m_1 = a_1+a_2$，$m_2 = \min(a_1+a_2, 0) = 0$，后面全 $0$）。
• 操作 $(2, 3)$（当 $n \ge 3$ 且 $a_1 \le a_2$）：$S_2 = a_1 + \min(a_1, a_2 + a_3)$。

进一步推导可知，对于所有情况，最小可能值就是 $\min(2a_1, a_1 + a_2)$。

原因：

• 若 $a_1 \le a_2$，不操作时 $m_1 = a_1$，$m_2 = a_1$，后面至少 $0$，总和 $\ge 2a_1$。
  操作 $(2,3)$ 可得 $a_1 + \min(a_1, a_2+a_3) \ge 2a_1$ 或更大，但无法小于 $2a_1$。
  而操作 $(1,2)$ 得到 $a_1 + a_2 \ge 2a_1$，所以最小为 $2a_1$（当 $a_1 \le a_2$ 时，$a_1+a_2 \ge 2a_1$，所以 $2a_1$ 更小或相等）。

• 若 $a_1 > a_2$，不操作时 $m_1 = a_1$，$m_2 = a_2$，后面至少 $0$，总和 $\ge a_1 + a_2$。
  操作 $(1,2)$ 得到 $a_1 + a_2$，且 $a_1+a_2 < 2a_1$（因为 $a_2 < a_1$），所以最小为 $a_1 + a_2$。

因此，答案统一为：

$$\boxed{\min(2a_1,\ a_1 + a_2)}.$$

---

第五步：边界情况

• 当 $n=2$ 时，无法操作 $(2,3)$，但上述公式仍然正确：
  若 $a_1 > a_2$，答案为 $a_1 + a_2$（操作 $(1,2)$）；
  若 $a_1 \le a_2$，不操作得 $a_1 + a_1 = 2a_1$，操作 $(1,2)$ 得 $a_1+a_2 \ge 2a_1$，所以最小为 $2a_1$。

• 当 $a_2 = 0$ 时，公式依然成立。

---

算法步骤

1. 读入 $n$ 和数组 $a$。
2. 输出 $\min(2a_1, a_1 + a_2)$。

---

时间复杂度

• 每个测试用例 $O(1)$（忽略输入）。
• 总复杂度 $O(\sum n)$，满足 $2\times 10^5$ 限制。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    cout << min(2 * a[0], a[0] + a[1]) << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

---

验证样例

测试用例	$a$	$2a_1$	$a_1+a_2$	$\min$	输出
1	$[1,2]$	2	3	2
2	$[1,2,3]$
3	$[3,0,2,3]$	6		3

与题目输出一致。

---

总结

本题的关键在于：

1. 理解操作如何影响前缀最小值序列。
2. 发现只有前两个元素真正影响最优值。
3. 得到简洁的闭式解 $\min(2a_1, a_1 + a_2)$。