310107: CF1783C. Yet Another Tournament
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Yet Another Tournament
题意翻译
有 $n$ 个选手，编号为 $1$ 至 $n$ ，每两个选手对战时，编号大的将会胜利。 你可以准备 $m$ 单位时间，每准备 $a_i$ 时间就可以赢 $i$ 号选手。 按胜利的总次数排名，求你最高多少名。题目描述
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 $ a_i $ 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 $ p_1, p_2, \dots, p_k $ , you need to spend $ a_{p_1} + a_{p_2} + \dots + a_{p_k} $ 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 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n \le 5 \cdot 10^5 $ ; $ 0 \le m \le \sum\limits_{i=1}^{n}{a_i} $ ) — the number of your opponents and the total time you have for preparation. The second line of each test case contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 1000 $ ), where $ a_i $ 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 \cdot 10^5 $ .
输出格式
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 $ .Input
题意翻译
有 $n$ 个选手，编号为 $1$ 至 $n$ ，每两个选手对战时，编号大的将会胜利。 你可以准备 $m$ 单位时间，每准备 $a_i$ 时间就可以赢 $i$ 号选手。 按胜利的总次数排名，求你最高多少名。Output
**另一个锦标赛**
**题意翻译**
有 $ n $ 个选手，编号为 $ 1 $ 至 $ n $ ，每两个选手对战时，编号大的将会胜利。你可以准备 $ m $ 单位时间，每准备 $ a_i $ 时间就可以赢 $ i $ 号选手。按胜利的总次数排名，求你最高多少名。
**题目描述**
你在参加另一个锦标赛。共有 $ n + 1 $ 名参赛者：你和其他 $ n $ 名对手，编号从 $ 1 $ 到 $ n $ 。
每两名参赛者将会恰好对战一次。如果对手 $ i $ 与对手 $ j $ 对战，当且仅当 $ i > j $ 时，$ i $ 胜利。
当对手 $ i $ 与你对战时，情况变得有点复杂。为了在对对手 $ i $ 的比赛中获胜，你需要至少准备 $ a_i $ 分钟 —— 否则，你会输给那个对手。
你总共有 $ m $ 分钟的时间来为比赛做准备，但你一次只能为一场比赛做准备。换句话说，如果你想战胜对手 $ p_1, p_2, \dots, p_k $ ，你需要花费 $ a_{p_1} + a_{p_2} + \dots + a_{p_k} $ 分钟来准备 —— 如果这个数字大于 $ m $ ，你无法同时战胜所有这些对手。
每个参赛者的最终排名等于赢得比赛次数严格更多的参赛者数量 $ + 1 $ 。例如，如果有 3 名参赛者各赢得 5 场比赛，1 名参赛者赢得 3 场比赛，2 名参赛者各赢得 1 场比赛，那么前三名参赛者将获得第 1 名，第四名获得第 4 名，最后两名获得第 5 名。
计算如果你不能为比赛准备超过 $ m $ 分钟，你可以达到的最低可能排名（越低越好）。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) —— 测试用例的数量。
每个测试用例的第一行包含两个整数 $ n $ 和 $ m $ ( $ 1 \le n \le 5 \cdot 10^5 $ ; $ 0 \le m \le \sum\limits_{i=1}^{n}{a_i} $ ) —— 你的对手数量和你的总准备时间。
每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 1000 $ )，其中 $ a_i $ 是你为了战胜第 $ i $ 个对手需要准备的时间。
保证所有测试用例中 $ n $ 的总和不超过 $ 5 \cdot 10^5 $ 。
**输出格式**
对于每个测试用例，如果总共不能为比赛准备超过 $ m $ 分钟，输出你可以获得的最低可能排名。
**输入输出样例**
**输入样例 #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
```
**说明**
在第一个测试用例中，你可以为所有对手做准备，因此你将赢得 4 场比赛并获得第 1 名，因为你的所有对手赢得的比赛不超过 3 场。
在第二个测试用例中，你可以准备对抗第二个对手并获胜。结果，你将获得 1 场胜利，对手 1 获得 1 场胜利，对手 2 获得 1 场胜利，对手 3 获得 3 场胜利。所以对手 3 将获得第 1 名，包括你在内的所有其他参赛者将获得第 2 名。
在第三个测试用案中，你没有时间准备，因此你将输掉所有比赛。由于每个对手至少赢得 1 场比赛，你将获得最后一名（第 6 名）。
在第四个测试用例中，你没有时间准备，但你仍然可以战胜第一个对手。结果，对手 1 没有胜利，你有 1 场胜利，而其他所有人至少有 2 场胜利。所以你的排名是第 4 名。**另一个锦标赛** **题意翻译** 有 $ n $ 个选手，编号为 $ 1 $ 至 $ n $ ，每两个选手对战时，编号大的将会胜利。你可以准备 $ m $ 单位时间，每准备 $ a_i $ 时间就可以赢 $ i $ 号选手。按胜利的总次数排名，求你最高多少名。 **题目描述** 你在参加另一个锦标赛。共有 $ n + 1 $ 名参赛者：你和其他 $ n $ 名对手，编号从 $ 1 $ 到 $ n $ 。 每两名参赛者将会恰好对战一次。如果对手 $ i $ 与对手 $ j $ 对战，当且仅当 $ i > j $ 时，$ i $ 胜利。 当对手 $ i $ 与你对战时，情况变得有点复杂。为了在对对手 $ i $ 的比赛中获胜，你需要至少准备 $ a_i $ 分钟 —— 否则，你会输给那个对手。 你总共有 $ m $ 分钟的时间来为比赛做准备，但你一次只能为一场比赛做准备。换句话说，如果你想战胜对手 $ p_1, p_2, \dots, p_k $ ，你需要花费 $ a_{p_1} + a_{p_2} + \dots + a_{p_k} $ 分钟来准备 —— 如果这个数字大于 $ m $ ，你无法同时战胜所有这些对手。 每个参赛者的最终排名等于赢得比赛次数严格更多的参赛者数量 $ + 1 $ 。例如，如果有 3 名参赛者各赢得 5 场比赛，1 名参赛者赢得 3 场比赛，2 名参赛者各赢得 1 场比赛，那么前三名参赛者将获得第 1 名，第四名获得第 4 名，最后两名获得第 5 名。 计算如果你不能为比赛准备超过 $ m $ 分钟，你可以达到的最低可能排名（越低越好）。 **输入输出格式** **输入格式** 第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) —— 测试用例的数量。 每个测试用例的第一行包含两个整数 $ n $ 和 $ m $ ( $ 1 \le n \le 5 \cdot 10^5 $ ; $ 0 \le m \le \sum\limits_{i=1}^{n}{a_i} $ ) —— 你的对手数量和你的总准备时间。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 1000 $ )，其中 $ a_i $ 是你为了战胜第 $ i $ 个对手需要准备的时间。 保证所有测试用例中 $ n $ 的总和不超过 $ 5 \cdot 10^5 $ 。 **输出格式** 对于每个测试用例，如果总共不能为比赛准备超过 $ m $ 分钟，输出你可以获得的最低可能排名。 **输入输出样例** **输入样例 #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 ``` **说明** 在第一个测试用例中，你可以为所有对手做准备，因此你将赢得 4 场比赛并获得第 1 名，因为你的所有对手赢得的比赛不超过 3 场。 在第二个测试用例中，你可以准备对抗第二个对手并获胜。结果，你将获得 1 场胜利，对手 1 获得 1 场胜利，对手 2 获得 1 场胜利，对手 3 获得 3 场胜利。所以对手 3 将获得第 1 名，包括你在内的所有其他参赛者将获得第 2 名。 在第三个测试用案中，你没有时间准备，因此你将输掉所有比赛。由于每个对手至少赢得 1 场比赛，你将获得最后一名（第 6 名）。 在第四个测试用例中，你没有时间准备，但你仍然可以战胜第一个对手。结果，对手 1 没有胜利，你有 1 场胜利，而其他所有人至少有 2 场胜利。所以你的排名是第 4 名。
**题意翻译**
有 $ n $ 个选手，编号为 $ 1 $ 至 $ n $ ，每两个选手对战时，编号大的将会胜利。你可以准备 $ m $ 单位时间，每准备 $ a_i $ 时间就可以赢 $ i $ 号选手。按胜利的总次数排名，求你最高多少名。
**题目描述**
你在参加另一个锦标赛。共有 $ n + 1 $ 名参赛者：你和其他 $ n $ 名对手，编号从 $ 1 $ 到 $ n $ 。
每两名参赛者将会恰好对战一次。如果对手 $ i $ 与对手 $ j $ 对战，当且仅当 $ i > j $ 时，$ i $ 胜利。
当对手 $ i $ 与你对战时，情况变得有点复杂。为了在对对手 $ i $ 的比赛中获胜，你需要至少准备 $ a_i $ 分钟 —— 否则，你会输给那个对手。
你总共有 $ m $ 分钟的时间来为比赛做准备，但你一次只能为一场比赛做准备。换句话说，如果你想战胜对手 $ p_1, p_2, \dots, p_k $ ，你需要花费 $ a_{p_1} + a_{p_2} + \dots + a_{p_k} $ 分钟来准备 —— 如果这个数字大于 $ m $ ，你无法同时战胜所有这些对手。
每个参赛者的最终排名等于赢得比赛次数严格更多的参赛者数量 $ + 1 $ 。例如，如果有 3 名参赛者各赢得 5 场比赛，1 名参赛者赢得 3 场比赛，2 名参赛者各赢得 1 场比赛，那么前三名参赛者将获得第 1 名，第四名获得第 4 名，最后两名获得第 5 名。
计算如果你不能为比赛准备超过 $ m $ 分钟，你可以达到的最低可能排名（越低越好）。
**输入输出格式**
**输入格式**
第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) —— 测试用例的数量。
每个测试用例的第一行包含两个整数 $ n $ 和 $ m $ ( $ 1 \le n \le 5 \cdot 10^5 $ ; $ 0 \le m \le \sum\limits_{i=1}^{n}{a_i} $ ) —— 你的对手数量和你的总准备时间。
每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 1000 $ )，其中 $ a_i $ 是你为了战胜第 $ i $ 个对手需要准备的时间。
保证所有测试用例中 $ n $ 的总和不超过 $ 5 \cdot 10^5 $ 。
**输出格式**
对于每个测试用例，如果总共不能为比赛准备超过 $ m $ 分钟，输出你可以获得的最低可能排名。
**输入输出样例**
**输入样例 #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
```
**说明**
在第一个测试用例中，你可以为所有对手做准备，因此你将赢得 4 场比赛并获得第 1 名，因为你的所有对手赢得的比赛不超过 3 场。
在第二个测试用例中，你可以准备对抗第二个对手并获胜。结果，你将获得 1 场胜利，对手 1 获得 1 场胜利，对手 2 获得 1 场胜利，对手 3 获得 3 场胜利。所以对手 3 将获得第 1 名，包括你在内的所有其他参赛者将获得第 2 名。
在第三个测试用案中，你没有时间准备，因此你将输掉所有比赛。由于每个对手至少赢得 1 场比赛，你将获得最后一名（第 6 名）。
在第四个测试用例中，你没有时间准备，但你仍然可以战胜第一个对手。结果，对手 1 没有胜利，你有 1 场胜利，而其他所有人至少有 2 场胜利。所以你的排名是第 4 名。**另一个锦标赛** **题意翻译** 有 $ n $ 个选手，编号为 $ 1 $ 至 $ n $ ，每两个选手对战时，编号大的将会胜利。你可以准备 $ m $ 单位时间，每准备 $ a_i $ 时间就可以赢 $ i $ 号选手。按胜利的总次数排名，求你最高多少名。 **题目描述** 你在参加另一个锦标赛。共有 $ n + 1 $ 名参赛者：你和其他 $ n $ 名对手，编号从 $ 1 $ 到 $ n $ 。 每两名参赛者将会恰好对战一次。如果对手 $ i $ 与对手 $ j $ 对战，当且仅当 $ i > j $ 时，$ i $ 胜利。 当对手 $ i $ 与你对战时，情况变得有点复杂。为了在对对手 $ i $ 的比赛中获胜，你需要至少准备 $ a_i $ 分钟 —— 否则，你会输给那个对手。 你总共有 $ m $ 分钟的时间来为比赛做准备，但你一次只能为一场比赛做准备。换句话说，如果你想战胜对手 $ p_1, p_2, \dots, p_k $ ，你需要花费 $ a_{p_1} + a_{p_2} + \dots + a_{p_k} $ 分钟来准备 —— 如果这个数字大于 $ m $ ，你无法同时战胜所有这些对手。 每个参赛者的最终排名等于赢得比赛次数严格更多的参赛者数量 $ + 1 $ 。例如，如果有 3 名参赛者各赢得 5 场比赛，1 名参赛者赢得 3 场比赛，2 名参赛者各赢得 1 场比赛，那么前三名参赛者将获得第 1 名，第四名获得第 4 名，最后两名获得第 5 名。 计算如果你不能为比赛准备超过 $ m $ 分钟，你可以达到的最低可能排名（越低越好）。 **输入输出格式** **输入格式** 第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) —— 测试用例的数量。 每个测试用例的第一行包含两个整数 $ n $ 和 $ m $ ( $ 1 \le n \le 5 \cdot 10^5 $ ; $ 0 \le m \le \sum\limits_{i=1}^{n}{a_i} $ ) —— 你的对手数量和你的总准备时间。 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \dots, a_n $ ( $ 0 \le a_i \le 1000 $ )，其中 $ a_i $ 是你为了战胜第 $ i $ 个对手需要准备的时间。 保证所有测试用例中 $ n $ 的总和不超过 $ 5 \cdot 10^5 $ 。 **输出格式** 对于每个测试用例，如果总共不能为比赛准备超过 $ m $ 分钟，输出你可以获得的最低可能排名。 **输入输出样例** **输入样例 #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 ``` **说明** 在第一个测试用例中，你可以为所有对手做准备，因此你将赢得 4 场比赛并获得第 1 名，因为你的所有对手赢得的比赛不超过 3 场。 在第二个测试用例中，你可以准备对抗第二个对手并获胜。结果，你将获得 1 场胜利，对手 1 获得 1 场胜利，对手 2 获得 1 场胜利，对手 3 获得 3 场胜利。所以对手 3 将获得第 1 名，包括你在内的所有其他参赛者将获得第 2 名。 在第三个测试用案中，你没有时间准备，因此你将输掉所有比赛。由于每个对手至少赢得 1 场比赛，你将获得最后一名（第 6 名）。 在第四个测试用例中，你没有时间准备，但你仍然可以战胜第一个对手。结果，对手 1 没有胜利，你有 1 场胜利，而其他所有人至少有 2 场胜利。所以你的排名是第 4 名。