← 返回题目列表

Codeforces · 2229/C1

C1. 我们正在翻转(简单版)

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

这是问题的简单版本。版本之间的差异在于,在此版本中,您必须最小化总和。只有解决了该问题的所有版本,您才能破解。

您有一个长度为 $$$n$$$ 的数组 $$$a$$$,它由非零(但可能是负数)整数组成。您最多将执行以下操作 $$$n$$$ 次(可能没有):

  • 选择索引 $$$i$$$ ($$$1 \le i \le n$$$) 使得 $$$a_i \gt 0$$$
  • 然后对于每个$$$j$$$,其中$$$1 \le j \le i$$$ 执行$$$a_j := -a_j$$$。

输出长度最多为 $$$n$$$ 的有效操作序列,其中 $$$\color{red}{\text{minimizes}}$$$ 最后的 $$$a$$$ 之和。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$-10^9 \le a_i \le 10^9, a_i \ne 0$$$)。

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

输出

对于每个测试用例,输出一个整数 $$$k$$$ ($$$0 \le k \le n$$$) - 您将执行的操作数。

现在输出 $$$k$$$ 整数 $$$b_1,\ldots,b_k$$$ 其中 $$$b_i$$$ 是您执行第 $$$i$$$ 操作的索引。

执行操作后,$$$a$$$ 的总和应该最小。

示例

输入
复制

3
5
-1 -2 -3 -5 -4
5
-1 -2 3 -5 4
4
5 7 10 19

输出
复制

0

4
3 5 4 2
1
4

注意

在第一个测试用例中,总和已经最小化。所以不需要任何操作。

在第二个测试用例中,操作如下:

  • $$$[-1, -2, 3, -5, 4] \xrightarrow{i = 3} [\color{红色}{1, 2, -3}, -5, 4]$$$
  • $$$[1, 2, -3, -5, 4] \xrightarrow{i = 5} [\color{红色}{-1, -2, 3, 5, -4}]$$$
  • $$$[-1, -2, 3, 5, -4] \xrightarrow{i = 4} [\color{红色}{1, 2, -3, -5}, -4]$$$
  • $$$[1, 2, -3, -5, -4] \xrightarrow{i = 2} [\color{红色}{-1, -2}, -3, -5, -4]$$$

其总和为 $$$-15$$$,这是可能的最小值。