P14123 [SCCPC 2021] Hourly Coding Problem

本题由 Ema 提出。 给定一个数字数组 $N$ 和一个整数 $k$，你的任务是将 $N$ 拆分为 $k$ 个非空连续子区间，使得所有子区间的区间和的最大值最小。输出每个子区间的长度。如果存在多种方案，输出字典序最大的方案。 如果存在整数 $i$（$1 \le i \le n$），使得方案 A 和方案 B 前 $i-1$ 个子区间长度相同，第 $i$ 个子区间 A 比 B 长，则认为方案 A 字典序大于 B。 例如，给定 $N = [5, 1, 0, 2, 7, -3, 4]$ 和 $k = 3$，应该输出 $[3, 3, 1]$，因为最优划分为 $[5, 1, 0]$，$[2, 7, -3]$，$[4]$。注意，这只是举例，实际输出格式见下文描述。

多组测试用例。输入的第一行包含一个整数 $T$，表示测试用例数量。 每个测试用例包含两行： 第一行包含两个整数 $n$ 和 $k$（$1 \le k \le n \le 3 \times 10^5$），表示数组长度及划分区间数。 第二行包含 $n$ 个整数 $N = [a_1, a_2, \cdots, a_n]$（$|a_i| \le 10^9$），表示数组元素。 保证所有测试用例中 $n$ 的总和不超过 $6 \times 10^5$。

对每个测试用例，输出一行 $k$ 个整数，表示每个分区的长度。注意，答案必须是字典序最大的可行方案。

由 ChatGPT 5 翻译