310165: CF1791G1. Teleporters (Easy Version)
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Teleporters (Easy Version)
题意翻译
有 $t$ 组数据,每次给出 $n$、$c$ 和 $n$ 个整数 $a_i$。 你现在在 $0$ 点,在 $1 \sim n$ 中每个点上都有一个传送器,**且每个传送器只能使用一次**,在点 $i$,可以执行如下操作: * 向左移动一个单位,花费 $1$ 硬币。 * 向右移动一个单位,花费 $1$ 硬币。 * 在点 $i$ 使用传送器,传送回到 $0$ 点,花费 $a_i$ 个硬币。 你有 $c$ 个硬币,求出从 $0$ 点出发,最多可以使用的传送器个数。题目描述
The only difference between the easy and hard versions are the locations you can teleport to. Consider the points $ 0, 1, \dots, n $ on the number line. There is a teleporter located on each of the points $ 1, 2, \dots, n $ . At point $ i $ , you can do the following: - Move left one unit: it costs $ 1 $ coin. - Move right one unit: it costs $ 1 $ coin. - Use a teleporter at point $ i $ , if it exists: it costs $ a_i $ coins. As a result, you teleport to point $ 0 $ . Once you use a teleporter, you can't use it again. You have $ c $ coins, and you start at point $ 0 $ . What's the most number of teleporters you can use?输入输出格式
输入格式
The input consists of multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. The descriptions of the test cases follow. The first line of each test case contains two integers $ n $ and $ c $ ( $ 1 \leq n \leq 2\cdot10^5 $ ; $ 1 \leq c \leq 10^9 $ ) — the length of the array and the number of coins you have respectively. The following line contains $ n $ space-separated integers $ a_1, a_2, \dots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — the costs to use the teleporters. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .
输出格式
For each test case, output the maximum number of teleporters you can use.
输入输出样例
输入样例 #1
10
5 6
1 1 1 1 1
8 32
100 52 13 6 9 4 100 35
1 1
5
4 5
4 3 2 1
5 9
2 3 1 4 1
5 8
2 3 1 4 1
4 3
2 3 4 1
4 9
5 4 3 3
2 14
7 5
5 600000000
500000000 400000000 300000000 200000000 100000000
输出样例 #1
2
2
0
1
2
2
1
1
1
2