CF1791G2 Teleporters (Hard Version)

本题的简单版与困难版的唯一区别在于你可以传送到的位置。 考虑数轴上的点 $0,1,\dots,n+1$。在每个点 $1,2,\dots,n$ 上都设有一个传送器。在第 $i$ 个点，你可以进行以下操作： - 向左移动一单位：花费 $1$ 个金币。 - 向右移动一单位：花费 $1$ 个金币。 - 使用第 $i$ 个点的传送器（如果存在）：花费 $a_i$ 个金币。你可以选择传送到点 $0$ 或点 $n+1$。每个传送器只能使用一次。 你有 $c$ 个金币，起始位置在点 $0$。你最多能使用多少个传送器？

输入包含多组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。接下来是每组测试数据的描述。 每组测试数据的第一行包含两个整数 $n$ 和 $c$（$1 \leq n \leq 2\cdot10^5$；$1 \leq c \leq 10^9$），分别表示数组的长度和你拥有的金币数。 接下来一行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n$（$1 \leq a_i \leq 10^9$），表示每个传送器的使用费用。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

对于每组测试数据，输出你最多能使用多少个传送器。

在第一个测试用例中，你可以向右移动一格，使用第 $1$ 个传送器传送到点 $n+1$，再向左移动一格，使用第 $5$ 个传送器。你剩下 $6-1-1-1-1=2$ 个金币，无论你传送到哪里，都不足以再使用一个传送器。你共使用了两个传送器，所以答案是 $2$。 在第二个测试用例中，你向右移动四格并使用传送器传送到 $n+1$，然后向左移动三格并使用第 $6$ 个传送器传送到 $n+1$，最后再向左移动四格并使用传送器。总花费为 $4+6+3+4+4+9=30$，你使用了三个传送器。 在第三个测试用例中，你的金币不足以使用任何传送器，所以答案是 $0$。 由 ChatGPT 4.1 翻译