CF1779C.Least Prefix Sum

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Baltic, a famous chess player who is also a mathematician, has an array $a_1,a_2, \ldots, a_n$ , and he can perform the following operation several (possibly $0$ ) times:

Choose some index $i$ ( $1 \leq i \leq n$ );
multiply $a_i$ with $-1$ , that is, set $a_i := -a_i$ .

Baltic's favorite number is $m$ , and he wants $a_1 + a_2 + \cdots + a_m$ to be the smallest of all non-empty prefix sums. More formally, for each $k = 1,2,\ldots, n$ it should hold that $$$$a_1 + a_2 + \cdots + a_k \geq a_1 + a_2 + \cdots + a_m. $$

Please note that multiple smallest prefix sums may exist and that it is only required that $a\_1 + a\_2 + \\cdots + a\_m$ is one of them.

Help Baltic find the minimum number of operations required to make $a\_1 + a\_2 + \\cdots + a\_m$ $$ the least of all prefix sums. It can be shown that a valid sequence of operations always exists.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \leq t \leq 10\,000$ ). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ( $1 \leq m \leq n \leq 2\cdot 10^5$ ) — the size of Baltic's array and his favorite number.

The second line contains $n$ integers $a_1,a_2, \ldots, a_n$ ( $-10^9 \leq a_i \leq 10^9$ ) — the array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$ .

输出格式

For each test case, print a single integer — the minimum number of required operations.

输入输出样例

输入#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

说明/提示

In the first example, we perform the operation $a_4 := -a_4$ . The array becomes $[-1,-2,-3,4]$ and the prefix sums, $[a_1, \ a_1+a_2, \ a_1+a_2+a_3, \ a_1+a_2+a_3+a_4]$ , are equal to $[-1,-3,-6,-2]$ . Thus $a_1 + a_2 + a_3=-6$ is the smallest of all prefix sums.

In the second example, we perform the operation $a_3 := -a_3$ . The array becomes $[1,2,-3,4]$ with prefix sums equal to $[1,3,0,4]$ .

In the third and fourth examples, $a_1 + a_2 + \cdots + a_m$ is already the smallest of the prefix sums — no operation needs to be performed.

In the fifth example, a valid sequence of operations is:

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

The array becomes $[-2,-3,5,-5,20]$ and its prefix sums are $[-2,-5,0,-5,15]$ . Note that $a_1+a_2=-5$ and $a_1+a_2+a_3+a_4=-5$ are both the smallest of the prefix sums (and this is a valid solution).

首页