D. 猫头鹰塞拉芬 详细题解

题目核心理解

有 $n$ 个人排队，基里尔排在最后。 他可以向前插队：

• 若从位置 $i$ 跳到位置 $j(j<i)$，需要支付 $a_j$ 给 $j$ 号人；
• 对中间每一个人 $k(j<k<i)$，需要支付 $b_k$；
• 要求最终排进前 $m$ 个位置； 求最小花费。

---

核心思路

1. 关键贪心观察

• 对于每个位置 $i$，只有两种代价：$a_i$ 和 $b_i$。
• 只要 $a_i < b_i$，在这里直接用 $a_i$ 一定更优，相当于一步跳到这里。
• 否则只能一路付 $b_i$ 过去。
• 大于 $m$ 的位置都必须经过，我们从后往前贪心选最小代价。
• 最后在前 $m$ 个位置里选一个终点，加上对应 $a_f$ 取最小总代价。

2. 步骤拆解

1. 从 $n$ 倒序遍历到 $m+1$：
   • 若 $a_i < b_i$：选 $a_i$，累加代价。
   • 否则：选 $b_i$，累加代价。
2. 遍历结束后，剩下只需要在前 $m$ 个位置选一个终点 $f$。
3. 总代价 = 已累加代价 + $a_f$，取最小值即为答案。

---

算法流程

1. 读入 $n, m$，数组 $a, b$。
2. 从 $i = n$ 到 $i = m+1$ 逆序遍历：
   • sum += min(a[i], b[i])
3. 枚举 $i = 1$ 到 $i = m$：
   • ans = min(ans, sum + a[i])
4. 输出 $ans$。

---

公式与复杂度分析

最终答案表达式：

$$ans = \min_{1\le f\le m}\left( \sum_{i=m+1}^n \min(a_i,b_i) \;+\; a_f \right) $$

复杂度

• 遍历数组两次，均为线性。
• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$ 可轻松通过 $n \le 2\times 10^5$、多组数据总和限制。