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

题目核心理解

一开始有 $n$ 个人排队，Kirill 站在第 $n+1$ 位（队尾）。 他可以多次向前插队，规则如下：

• 若当前在位置 $i$，可以跳到任意前面位置 $j(j<i)$；
• 要给 $j$ 位置的人支付 $a_j$；
• 对中间每一个人 $k(j<k<i)$，支付 $b_k$；
• 要求最终停在前 $m$ 个位置（$1\le f\le m$）； 求最少花费金币数。

核心思路

1. 关键贪心观察

对于任意一个人 $k$：

• 如果 $b_k > a_k$：只给他付 $b_k$ 是不划算的，应该尽量直接交换到这里，只付 $a_k$；
• 如果 $b_k < a_k$：经过他时付 $b_k$ 更便宜，没必要专门交换。

所以最优策略是：

• 只在满足 $a_j < b_j$ 且 $j>m$ 的位置交换；
• 这些位置能跳就跳，能最大程度省钱；
• 跳到不能再跳时，直接枚举前 $m$ 个位置取最小花费。

2. 花费计算

从 $i$ 跳到 $j$ 的花费为：

用前缀和可以 $O(1)$ 求出区间 $b$ 的和。

3. 最终收尾

当前方没有满足 $a_j < b_j$ 且 $j>m$ 的位置时：

• 直接枚举 $1\sim m$ 所有位置；
• 计算停在每个位置的总花费；
• 取最小值即为答案。

算法流程

1. 预处理 $b$ 数组的前缀和 $sum_b$；
2. 从队尾 $now = n+1$ 开始向前贪心跳跃；
3. 每次寻找第一个 $j<now$，满足 $a_j < b_j$ 且 $j>m$；
4. 若找到，计算跳跃花费并更新最小值，将 $now$ 设为 $j$；
5. 若找不到，退出贪心阶段；
6. 从当前位置向前遍历到 $1$，累加 $b_k$，并对所有 $f\le m$ 更新最小花费；
7. 输出最小花费。

公式与复杂度分析

单次跳跃花费：

遍历过程总花费递推：

对 $f\le m$ 用 $total+a_f$ 更新答案。

复杂度

• 前缀和预处理：$O(n)$
• 贪心跳跃：每个位置至多访问一次 $O(n)$
• 最后遍历：$O(n)$

总时间复杂度：$O(n)$。 可轻松处理 $n\le 2\times 10^5$、多组数据总长度不超过 $2\times 10^5$ 的范围。