#P14123. [SCCPC 2021] Hourly Coding Problem

[SCCPC 2021] Hourly Coding Problem

题目描述

This problem was asked by Ema.

Given an array of numbers NN and an integer kk, your task is to split NN into kk non-empty consecutive partitions such that the maximum sum of any partition is minimized. Output the length of each of the kk partitions. If there are multiple solutions, output the solution with the largest lexicographical order.

Solution A is considered to be lexicographically larger than Solution B if there exists an integer ii(1in1 \le i \le n), where the first i1i-1 partitions in A and B have the same length, and the iith partition in A is longer than that in B.

For example, given N=[5,1,0,2,7,3,4]N = [5, 1, 0, 2, 7, -3, 4] and k=3k = 3, you should output [3,3,1][3, 3, 1], since the optimal partition is [5,1,0],[2,7,3],[4][5, 1, 0], [2, 7, -3], [4]. Note that this example used this format solely for convenience, your program should follow the format described below.

输入格式

There are multiple test cases. The first line of the input contains an integer TT indicating the number of test cases. For each test case:

The first line contains two integers nn and kk (1kn3×1051 \le k \le n \le 3 \times 10^5) indicating the length of the array and the number of partitions.

The next line contains nn integer N=[a1,a2,,an]N = [a_1, a_2, \cdots, a_n] (ai109|a_i| \le 10^9) indicating the array.

It's guaranteed that the sum of nn of all test cases will not exceed 6×1056 \times 10^5.

输出格式

For each test case, output one line containing kk integers indicating the length of each of the kk partitions. Note again that your answer must be the lexicographically largest answer.

3
7 3
5 1 0 2 7 -3 4
6 4
-1 3 -2 4 -3 5
6 2
0 -2 0 -1 -1 0
3 3 1
1 1 2 2
3 3