A10616 | Contest Balloons
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
One tradition of ACM-ICPC contests is that a team gets a balloon for every solved problem. We assume that the submission time doesn't matter and teams are sorted only by the number of balloons they have. It means that one's place is equal to the number of teams with more balloons, increased by $1$ . For example, if there are seven teams with more balloons, you get the eight place. Ties are allowed.
You should know that it's important to eat before a contest. If the number of balloons of a team is greater than the weight of this team, the team starts to float in the air together with their workstation. They eventually touch the ceiling, what is strictly forbidden by the rules. The team is then disqualified and isn't considered in the standings.
A contest has just finished. There are $n$ teams, numbered $1$ through $n$ . The $i$ -th team has $t_{i}$ balloons and weight $w_{i}$ . It's guaranteed that $t_{i}$ doesn't exceed $w_{i}$ so nobody floats initially.
Limak is a member of the first team. He doesn't like cheating and he would never steal balloons from other teams. Instead, he can give his balloons away to other teams, possibly making them float. Limak can give away zero or more balloons of his team. Obviously, he can't give away more balloons than his team initially has.
What is the best place Limak can get?
You should know that it's important to eat before a contest. If the number of balloons of a team is greater than the weight of this team, the team starts to float in the air together with their workstation. They eventually touch the ceiling, what is strictly forbidden by the rules. The team is then disqualified and isn't considered in the standings.
A contest has just finished. There are $n$ teams, numbered $1$ through $n$ . The $i$ -th team has $t_{i}$ balloons and weight $w_{i}$ . It's guaranteed that $t_{i}$ doesn't exceed $w_{i}$ so nobody floats initially.
Limak is a member of the first team. He doesn't like cheating and he would never steal balloons from other teams. Instead, he can give his balloons away to other teams, possibly making them float. Limak can give away zero or more balloons of his team. Obviously, he can't give away more balloons than his team initially has.
What is the best place Limak can get?
输入格式
The first line of the standard input contains one integer $n$ ( $2<=n<=300000$ ) — the number of teams.
The $i$ -th of $n$ following lines contains two integers $t_{i}$ and $w_{i}$ ( $0<=t_{i}<=w_{i}<=10^{18}$ ) — respectively the number of balloons and the weight of the $i$ -th team. Limak is a member of the first team.
The $i$ -th of $n$ following lines contains two integers $t_{i}$ and $w_{i}$ ( $0<=t_{i}<=w_{i}<=10^{18}$ ) — respectively the number of balloons and the weight of the $i$ -th team. Limak is a member of the first team.
输出格式
Print one integer denoting the best place Limak can get.
输入输出样例
输入 #1
8 20 1000 32 37 40 1000 45 50 16 16 16 16 14 1000 2 1000
输出 #1
3
输入 #2
7 4 4 4 4 4 4 4 4 4 4 4 4 5 5
输出 #2
2
输入 #3
7 14000000003 1000000000000000000 81000000000 88000000000 5000000000 7000000000 15000000000 39000000000 46000000000 51000000000 0 1000000000 0 0
输出 #3
2
In the first sample, Limak has $20$ balloons initially. There are three teams with more balloons ( $32$ , $40$ and $45$ balloons), so Limak has the fourth place initially. One optimal strategy is:
1. Limak gives $6$ balloons away to a team with $32$ balloons and weight $37$ , which is just enough to make them fly. Unfortunately, Limak has only $14$ balloons now and he would get the fifth place.
2. Limak gives $6$ balloons away to a team with $45$ balloons. Now they have $51$ balloons and weight $50$ so they fly and get disqualified.
3. Limak gives $1$ balloon to each of two teams with $16$ balloons initially.
4. Limak has $20-6-6-1-1=6$ balloons.
5. There are three other teams left and their numbers of balloons are $40$ , $14$ and $2$ .
6. Limak gets the third place because there are two teams with more balloons.
In the second sample, Limak has the second place and he can't improve it.
In the third sample, Limak has just enough balloons to get rid of teams $2$ , $3$ and $5$ (the teams with $81000000000$ , $5000000000$ and $46000000000$ balloons respectively). With zero balloons left, he will get the second place (ex-aequo with team $6$ and team $7$ ).
1. Limak gives $6$ balloons away to a team with $32$ balloons and weight $37$ , which is just enough to make them fly. Unfortunately, Limak has only $14$ balloons now and he would get the fifth place.
2. Limak gives $6$ balloons away to a team with $45$ balloons. Now they have $51$ balloons and weight $50$ so they fly and get disqualified.
3. Limak gives $1$ balloon to each of two teams with $16$ balloons initially.
4. Limak has $20-6-6-1-1=6$ balloons.
5. There are three other teams left and their numbers of balloons are $40$ , $14$ and $2$ .
6. Limak gets the third place because there are two teams with more balloons.
In the second sample, Limak has the second place and he can't improve it.
In the third sample, Limak has just enough balloons to get rid of teams $2$ , $3$ and $5$ (the teams with $81000000000$ , $5000000000$ and $46000000000$ balloons respectively). With zero balloons left, he will get the second place (ex-aequo with team $6$ and team $7$ ).
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted