← 返回题目列表

Codeforces · 2061/I

I. 凯文和尼维克

中文机器翻译题面 查看原题

凯文和尼维克正在争夺“最佳凯文”的称号。他们的目标是通过 $$$n$$$ 比赛来确定获胜者。

第 $$$i$$$ 匹配可以是以下两种类型之一:

- 类型 1:Kevin 需要花费 $$$a_i$$$ 时间来击败 Nivek 并赢得比赛。如果凯文不花 $$$a_i$$$ 时间,尼维克将赢得比赛。
- Type 2: The outcome of this match depends on their historical records.如果截至本场比赛凯文的胜场数大于或等于尼维克的胜场数,则凯文获胜。否则,尼维克获胜。

Kevin 想知道他需要花费多少时间来确保他至少赢得 $$$k$$$ 场比赛。

输出 $$$k = 0, 1, \ldots, n$$$ 的答案。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — 匹配数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \leq a_i \leq 10^9$$$)。

如果$$$a_i = -1$$$,则第 $$$i$$$ 场比赛属于类型 2。否则,第 $$$i$$$ 场比赛属于类型 1,$$$a_i$$$ 表示 Kevin 赢得这场比赛所需花费的时间。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出 $$$n + 1$$$ 整数。 The $$$i$$$-th integer represents the minimum amount of time to win at least $$$i-1$$$ matches.

示例

输入 #1

3
5
-1 -1 -1 -1 -1
5
3 2 5 4 1
5
100 -1 -1 -1 1

输出 #1

0 0 0 0 0 0 
0 1 3 6 10 15 
0 1 100 100 100 101

注意

在第一个测试用例中,所有比赛都是类型 2。Kevin 可以自动赢得所有比赛。

In the second test case, all matches are of Type 1. Kevin can choose matches in increasing order of $$$a_i$$$.

在第三个测试用例中:

- 如果凯文在 $$$1$$$ 比赛中花费 $$$a_1$$$ 时间,他可以赢得 $$$1, 2, 3, 4$$$ 比赛。
- 如果 Kevin 在 $$$5$$$ 比赛中花费 $$$a_5$$$ 时间,他可以赢得 $$$5$$$ 比赛。
- If Kevin spends $$$a_1$$$ time on match $$$1$$$ and $$$a_5$$$ time on match $$$5$$$, he can win all matches.