← 返回题目列表

Codeforces · 2053/I1

I1. 深情阵(简易版)

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

这是问题的简单版本。版本之间的区别在于,在此版本中,您需要计算数组的最小长度。只有解决了该问题的所有版本,您才能破解。

Iris 珍藏着一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。她知道这个数组有一个有趣的属性:所有元素的最大绝对值小于或等于所有元素的总和,即$$$\max(\lvert a_i\rvert) \leq \sum a_i$$$。

Iris 将数组的无聊度定义为其最大子数组$$$^{\text{*}}$$$ 之和。

Iris 的生日快到了,Victor 准备送她另一个数组 $$$b_1, b_2, \ldots, b_m$$$ 作为礼物。由于一些看似显而易见的原因,他决定数组 $$$b_1, b_2, \ldots, b_m$$$ 应该具有以下属性。

- $$$a_1, a_2, \ldots, a_n$$$ 应该是 $$$b_1, b_2, \ldots, b_m$$$ 的子序列$$$^{\text{†}}$$$。
- 两个数组的总和相同。即 $$$\sum\limits_{i=1}^n a_i = \sum\limits_{i=1}^m b_i$$$。
- $$$b_1, b_2, \ldots, b_m$$$ 的无聊度是最小的。
- 在无聊度最小的数组中,数组 $$$b$$$ 的长度(即 $$$m$$$)是最小的。而这样的话,艾丽丝就会第一时间明白他的心思!

即使受到上述限制,可能的礼物仍然太多。因此,Victor 要求您计算满足上述所有条件的任意数组 $$$b_1, b_2, \ldots, b_m$$$ 的 $$$\boldsymbol{m}$$$ 的值。他向你承诺:如果你成功帮助他,他将与你分享艾丽丝的生日蛋糕。

注意:由于输入较大,因此可能需要针对此问题进行优化。

例如,在 C++ 中,在 main() 函数的开头使用以下几行就足够了:

输入

每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 3\cdot 10^6$$$) — 数组 $$$a_1, a_2, \ldots, a_n$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) - 初始数组。保证 $$$\max(\lvert a_i\rvert) \leq \sum a_i$$$。

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

输出

对于每个测试用例,输出一行包含一个整数:有效数组 $$$b$$$ 的长度 $$$m$$$。

示例

输入 #1

4
4
1 2 3 4
4
2 -3 2 2
10
2 -7 6 3 -1 4 2 -5 8 -4
20
4 -2 4 3 -2 1 5 2 3 6 -5 -1 -4 -2 -3 5 -3 1 -4 1

输出 #1

4
6
14
25

注意

在第一个测试用例中,$$$a=[1, 2, 3, 4]$$$。唯一满足上述所有属性的数组$$$b$$$是$$$[1, 2, 3, 4]$$$,所以我们应该输出$$$4$$$。

在第二个测试用例中,$$$a=[2, -3, 2, 2]$$$。可能的数组$$$b$$$是$$$[1, 2, -3, 2, -1, 2]$$$和$$$[2, 1, -3, 2, -1, 2]$$$,所以我们应该输出$$$6$$$。