CF1779C Least Prefix Sum

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 10000$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $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$。

对于每个测试用例，输出一个整数，表示所需的最小操作次数。

在第一个样例中，我们执行操作 $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$ 都是最小的前缀和（这也是一个合法解）。 由 ChatGPT 4.1 翻译