用双指针维护当前仍在两端的船:左指针 i 指向当前最左存活船,右指针 j 指向当前最右存活船;并维护当前轮到“左端先打”还是“右端先打”的布尔量 left(初始为“左端先打”,即 left=true)。
设当前两端剩余耐久分别为 L(即 ai 的剩余)与 R(即 aj 的剩余)。从当前轮次开始,攻击顺序是严格左右交替,因此:
据此可以 一次性 计算让某一端被打沉所需的最少攻击次数:
n 艘船出发去探索海洋深处。这些船编号从 1 到 n ,按升序依次排列;第 i 艘船的耐久度为 ai 。
海怪按特定顺序对这些船发动了 k 次攻击。首先,它攻击第一艘船,然后是最后一艘,接着又攻击第一艘,依此类推。
海怪的每次攻击都会使船的耐久度降低 1 。当船的耐久度降至 0 时,它就会沉没,不再受到攻击(因此该船不再是第一艘或最后一艘,海怪只会攻击尚未沉没的船)。如果所有船都沉没了,海怪就没有可攻击的目标,便会游走。
例如,如果 n=4,k=5,且 a=[1,2,4,3] ,将会发生以下情况:
海怪攻击第一艘船,其耐久度变为 0 ,现在 a=[2,4,3] ;
海怪攻击最后一艘船,现在 a=[2,4,2] ;
海怪攻击第一艘船,现在 a=[1,4,2] ;
海怪攻击最后一艘船,现在 a=[1,4,1] ;
海怪攻击第一艘船,其耐久度变为 0 ,现在 a=[4,1] 。
请问海怪攻击后有多少艘船沉没了?
输入包括多组测试数据。
第一行包含一个整数 t(1≤t≤104) 表示测试数据的组数。
对于每个测试用例:
第一行包含两个整数 n 和 k(1≤n≤2∗105,1≤k≤1015) ,表示船的数量以及海怪攻击船的次数。
第二行包含 n 个整数 a1,a2,…,an(1≤ai≤109) ,表示船的耐久度。
对于每个测试用例,在单独的一行中输出被海怪击沉的船的数量。
输入
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