题目描述

难度分:$1300$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。
每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，$k(1 \leq k \leq 10^{15})$和长为$n$的数组$a(1 \leq a[i] \leq 19^9)$。

有$n$个石子堆，每堆的石子个数记录在数组$a$中。按照如下顺序取石子：

从最左边的有石子的堆中取出一颗石子，然后从最右边的有石子的堆中取出一颗石子，重复上述过程，左右左右取石子。你至多取出$k$颗石子。

你可以把多少堆石子变成空的？

输入样例

6
4 5
1 2 4 3
4 6
1 2 4 3
5 20
2 7 1 8 2
2 2
3 2
2 15
1 5
2 7
5 2

输出样例

2
3
5
0
2
2

算法

数学

如果$a$的总和$\leq k$，那肯定所有石子堆都能被清空，直接打印$n$。

对于一般情况，由于是左右左右的顺序取石子，因此左边取出的石子数量$\geq$右边取出的石子数量。最终$k$次操作中有$left=\lceil \frac{k}{2} \rceil$个石子是左边取出来的，$right=\lfloor \frac{k}{2} \rfloor$个石子是右边取出来的。其中$\lceil .\rceil$表示对$.$向上取整，$\lfloor . \rfloor$表示对$.$向下取整。

确定了左右两边取出的石子数就好办了，我们找到满足$\Sigma_{i \in [1,l]}a[i] \leq left$的最大$l$，再找到满足$\Sigma_{i \in [r,n]}a[i] \leq right$的最小$r$即可，清空的石子堆就是$[1,l]$和$[r,n]$，答案为$l+n-r+1$。

复杂度分析

时间复杂度

找到$l$和$r$只需要正序遍历一下$a$数组（求前缀和），再倒序遍历一下$a$数组（求后缀和）即可。而这两次遍历是可以提前退出的，$\Sigma_{i \in [1,n]}a[i] \gt k$保证$l \lt r$成立，因此时间复杂度为$O(n)$。

空间复杂度

除了输入的数组$a$，仅使用了有限几个变量，因此额外空间复杂度为$O(1)$。

$python$代码

t = int(input())
for _ in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    s = sum(a)
    if s <= k:
        print(n)
    else:
        left = k + 1 >> 1
        right = k - left
        l, ls = 0, 0
        for i in range(n):
            ls += a[i]
            if ls <= left:
                l = i + 1
            else:
                break
        r, rs = 0, 0
        for i in range(n - 1, -1, -1):
            rs += a[i]
            if rs <= right:
                r = n - i
            else:
                break
        print(l + r)