CF1783C.Yet Another Tournament
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
You are participating in Yet Another Tournament. There are n+1 participants: you and n other opponents, numbered from 1 to n .
Each two participants will play against each other exactly once. If the opponent i plays against the opponent j , he wins if and only if i>j .
When the opponent i plays against you, everything becomes a little bit complicated. In order to get a win against opponent i , you need to prepare for the match for at least ai minutes — otherwise, you lose to that opponent.
You have m minutes in total to prepare for matches, but you can prepare for only one match at one moment. In other words, if you want to win against opponents p1,p2,…,pk , you need to spend ap1+ap2+⋯+apk minutes for preparation — and if this number is greater than m , you cannot achieve a win against all of these opponents at the same time.
The final place of each contestant is equal to the number of contestants with strictly more wins + 1 . For example, if 3 contestants have 5 wins each, 1 contestant has 3 wins and 2 contestants have 1 win each, then the first 3 participants will get the 1 -st place, the fourth one gets the 4 -th place and two last ones get the 5 -th place.
Calculate the minimum possible place (lower is better) you can achieve if you can't prepare for the matches more than m minutes in total.
输入格式
The first line contains a single integer t ( 1≤t≤104 ) — the number of test cases.
The first line of each test case contains two integers n and m ( 1≤n≤5⋅105 ; 0≤m≤i=1∑nai ) — the number of your opponents and the total time you have for preparation.
The second line of each test case contains n integers a1,a2,…,an ( 0≤ai≤1000 ), where ai is the time you need to prepare in order to win against the i -th opponent.
It's guaranteed that the total sum of n over all test cases doesn't exceed 5⋅105 .
输出格式
For each test case, print the minimum possible place you can take if you can prepare for the matches no more than m minutes in total.
输入输出样例
输入#1
5 4 401 100 100 200 1 3 2 1 2 3 5 0 1 1 1 1 1 4 0 0 1 1 1 4 4 1 2 2 1
输出#1
1 2 6 4 1
说明/提示
In the first test case, you can prepare to all opponents, so you'll win 4 games and get the 1 -st place, since all your opponents win no more than 3 games.
In the second test case, you can prepare against the second opponent and win. As a result, you'll have 1 win, opponent 1 — 1 win, opponent 2 — 1 win, opponent 3 — 3 wins. So, opponent 3 will take the 1 -st place, and all other participants, including you, get the 2 -nd place.
In the third test case, you have no time to prepare at all, so you'll lose all games. Since each opponent has at least 1 win, you'll take the last place (place 6 ).
In the fourth test case, you have no time to prepare, but you can still win against the first opponent. As a result, opponent 1 has no wins, you have 1 win and all others have at least 2 wins. So your place is 4 .