官方题解

题目大意

一共有 $n$ 个关卡，每个关卡分为解密和战斗两部分，挑战关卡有两个限制：

• 对于不同关卡，只有完成了前一关的解密部分才能进行下一关的解密部分；

• 对于同一关卡，只有完成了这一关卡的解密部分才能进行这一关的战斗部分。

第 $i$ 关的解密部分需要耗时 $a_i$ ，战斗部分需要耗时 $b_i$ ，完成了一关的揭秘和战斗部分才视为完成这一关。对于 $q$ 个询问，求完成 $k$ 个关卡的最短用时。

解题思路

首先考虑完成 $k$ 个关卡，我们需要至少完成前 $k$ 个解密部分 ，完成 $b_i$ 之前我们需要至少完成前 $i$ 个解密部分。

接下来我们需要考虑的是选择完成哪几个关卡所花的时间最少。由于询问次数只有 $100$ ，所以对于每一个询问可以尝试使用 $O(n)$ 甚至 $O(nlogn)$ 的复杂度去完成。由于完成解密部分一定是连续的，所以我们可以先用前缀和 $s_i$ 求出前 $i$ 个解密部分所花时间是多少。

我们可以枚举最后一个被完成的关卡的哪个，此时的时间花费是 $s_i+b_i$ ，其余的 $k-1$ 个战斗部分选择 $b_i$ 最小的 $k-1$ 个，但是这样的做法时间复杂度会来到 $O(n^2)$ ，显然是不合理的。其实我们可以通过优先队列优化选 $b_i$ 的过程，我们先选出前 $k$ 关卡完成，将 $b_i$ 都存入优先队列中，往后枚举时，设当前枚举的位置为 $j$ ，如果 $b_j$ 小于优先队列中最大的元素，则可以把 $b_j$ 与优先队列中最大元素替换。每次算出所需要的时间，更新答案。这样查询的时间复杂度为 $O(nlogn)$ 。

总时间复杂度为 $O(n+knlogn)$ 。