Hello 2023

C. Least Prefix Sum

https://codeforces.com/contest/1779/problem/C

2 seconds / 256 megabytes

standard input / standard output

## Problem

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.

## Input

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$.

## Output

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

## Example

Input

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

Output

1
1
0
0
3
4

## Note

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).

## 代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;

const int MAXN = 2e5 + 10;
int n, m;
int a[MAXN], ps[MAXN];

void solve()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++)
ps[i] = ps[i - 1] + a[i];
int psm = ps[m], cnt = 0, offset = 0;
priority_queue<int> big_heap;
for (int i = m; i >= 1; i--)
{
while (ps[i] < psm + offset)
{
cnt++;
offset -= big_heap.top() * 2;
big_heap.pop();
}
if (a[i] > 0)
big_heap.push(a[i]);
}
priority_queue<int, vector<int>, greater<int>> small_heap;
offset = 0;
for (int i = m + 1; i <= n; i++)
{
if (a[i] < 0)
small_heap.push(a[i]);
while (ps[i] + offset < psm)
{
cnt++;
offset -= small_heap.top() * 2;
small_heap.pop();
}
}
cout << cnt << endl;
}

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}