#C4008. Maximum People on a Roller Coaster
Maximum People on a Roller Coaster
Maximum People on a Roller Coaster
You are given several test cases. For each test case, you are provided with two positive integers \(N\) and \(L\). Here, \(N\) represents the number of people and \(L\) is the maximum weight limit of the roller coaster. You then receive \(N\) integers indicating the weights of each person. Your task is to determine the maximum number of people that can safely board the roller coaster without the total weight exceeding \(L\). To achieve this, a greedy algorithm which sorts the weights in non-decreasing order and selects people until the weight limit is reached is recommended.
Note: The optimal strategy is to board the persons with lower weights first so as to maximize the count.
inputFormat
The input is read from stdin
and is formatted as follows:
- The first line contains an integer \(T\), the number of test cases.
- For each test case:
- The first line contains two integers \(N\) and \(L\) separated by a space, where \(N\) is the number of people and \(L\) is the weight limit.
- The second line contains \(N\) integers representing the weights of the people, separated by spaces.
outputFormat
The output should be printed to stdout
. For each test case, output a single line containing the maximum number of people that can board the roller coaster without exceeding the weight limit \(L\).
3
5 10
1 2 3 4 5
4 15
10 2 2 5
6 5
1 1 1 1 1 1
4
3
5
</p>