← 返回题目列表

Codeforces · 1779/C

C. 最小前缀和

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

Baltic是一位著名的国际象棋棋手,同时也是一位数学家,他有一个数组$$$a_1,a_2, \ldots, a_n$$$,他可以执行以下操作多次(可能是$$$0$$$):

- 选择一些索引 $$$i$$$ ($$$1 \leq i \leq n$$$);
- 将 $$$a_i$$$ 与 $$$-1$$$ 相乘,即设置 $$$a_i := -a_i$$$。

Baltic 最喜欢的数字是 $$$m$$$,他希望 $$$a_1 + a_2 + \cdots + a_m$$$ 成为所有非空前缀和中最小的。更正式地说,对于每个 $$$k = 1,2,\ldots, n$$$,它应该保持 $$$$$$a_1 + a_2 + \cdots + a_k \geq a_1 + a_2 + \cdots + a_m。$$$$$$

请注意,可能存在多个最小前缀和,只需$$$a_1 + a_2 + \cdots + a_m$$$ 是其中之一即可。

帮助 Baltic 找到使 $$$a_1 + a_2 + \cdots + a_m$$$ 成为所有前缀和最少所需的最少操作数。可以证明,有效的操作序列始终存在。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq m \leq n \leq 2\cdot 10^5$$$) - Baltic 数组的大小和他最喜欢的数字。

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

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

输出

对于每个测试用例,打印一个整数 - 所需操作的最少数量。

示例

输入 #1

6
4 3
-1 -2 -3 -4
4 3
1 2 3 4
1 1
1
5 5
-2 3 -5 1 -20
5 2
-2 3 -5 -5 -20
10 4
345875723 -48 384678321 -375635768 -35867853 -35863586 -358683842 -81725678 38576 -357865873

输出 #1

1
1
0
0
3
4

注意

在第一个示例中,我们执行操作 $$$a_4 := -a_4$$$。该数组变为 $$$[-1,-2,-3,4]$$$,前缀和 $$$[a_1, \ a_1+a_2, \ a_1+a_2+a_3, \ a_1+a_2+a_3+a_4]$$$ 等于 $$$[-1,-3,-6,-2]$$$。因此 $$$a_1 + a_2 + a_3=-6$$$ 是所有前缀和中最小的。

在第二个示例中,我们执行操作 $$$a_3 := -a_3$$$。该数组变为 $$$[1,2,-3,4]$$$,前缀和等于 $$$[1,3,0,4]$$$。

在第三个和第四个示例中,$$$a_1 + a_2 + \cdots + a_m$$$ 已经是最小的前缀和 - 不需要执行任何操作。

在第五个示例中,有效的操作顺序是:

- $$$a_3 := -a_3$$$,
- $$$a_2 := -a_2$$$,
- $$$a_5 := -a_5$$$。

数组变为 $$$[-2,-3,5,-5,20]$$$,其前缀和为 $$$[-2,-5,0,-5,15]$$$。请注意, $$$a_1+a_2=-5$$$ 和 $$$a_1+a_2+a_3+a_4=-5$$$ 都是最小的前缀和(这是一个有效的解决方案)。