| 题目名称 | 3202. 叠罗汉 |
|---|---|
| 输入输出 | dlh.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 syzhaoss
于2019-06-27加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：12， 提交：22， 通过率：54.55% | ||||
 lihaoze |
100 | 0.000 s | 0.00 MiB | C++ |
|
lihaoze |
100 | 0.002 s | 0.61 MiB | C++ |
|
syzhaoss |
100 | 0.018 s | 1.22 MiB | C++ |
|
0429 |
100 | 0.055 s | 1.83 MiB | C++ |
|
dew52 |
100 | 0.058 s | 2.52 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.066 s | 1.84 MiB | C++ |
|
dew52 |
100 | 0.067 s | 1.83 MiB | C++ |
 Hale |
100 | 0.076 s | 1.84 MiB | C++ |
|
dew52 |
100 | 0.086 s | 1.89 MiB | C++ |
|
dew52 |
100 | 0.097 s | 2.52 MiB | C++ |
| 关于 叠罗汉 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
自己YY出了一种贪心做法，可是怎么证明呀。。。。@5801 求大佬教
| ||||
|
林荫已提供一组HACK数据
瑆の時間~無盡輪迴·林蔭
2019-06-29 10:37
1楼
| ||||
【题目描述】
有$n$($2\leq n\leq 50000$)个罗汉，第$i$个罗汉的重量为$a_1$($1\leq a_i\leq 10000$) ，托举力量为$b_i$($1\leq b_i \leq 10^9$)，求最多能选出多少个罗汉，使得他们按照某种方式叠起来后，前$i-1$和罗汉的总重量不超过第$i$个罗汉的托举力量。
【输入格式】
第一行一个整数$n$表示罗汉的数目。
接下来n行，每行两个整数$a_i,b_i$，分别表示罗汉的重量和托举力量。
【输出格式】
一个整数，表示最多能有多少个罗汉叠起来。
【样例输入1】
3 1 2 6 9 2 4
【样例输出2】
3
【样例输入2】
4 4 2 5 3 6 4 2 3
【样例输出2】
2