CF1837F Editorial for Two

Berland 校际竞赛刚刚结束。Monocarp 和 Polycarp 作为评测委员会成员，准备进行题解讲解。不幸的是，时间有限，他们必须在闭幕式前完成。 比赛共有 $n$ 道题目，题目编号从 $1$ 到 $n$。第 $i$ 道题目的题解讲解需要 $a_i$ 分钟。Monocarp 和 Polycarp 计划只讲解其中恰好 $k$ 道题目。 讲解流程如下：他们面前有完整的 $n$ 道题目，按顺序排列。他们将移除 $n-k$ 道题目，剩下的 $k$ 道题目的顺序保持不变。然后，Monocarp 选择这些 $k$ 道题目的某个前缀（可以为空，也可以是全部），Polycarp 负责剩下的后缀。之后，他们分别去不同的房间并行讲解各自负责的题目。因此，整个讲解所需的时间等于两人中用时较长者的时间。 请帮助 Monocarp 和 Polycarp 选择要讲解的 $k$ 道题目及分配方式，使得讲解总时间最短。输出最短所需时间。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数量。 每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 3 \cdot 10^5$），分别表示题目总数和要讲解的题目数。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示每道题目的讲解时间。 所有测试用例中 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示在最优选择 $k$ 道题目及分配方式后，讲解所需的最短时间。

由 ChatGPT 4.1 翻译