| 题目名称 | 1036. [Citric S1] 柠檬的坦克游戏 |
|---|---|
| 输入输出 | lemon2.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-08-21加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：4， 提交：13， 通过率：30.77% | ||||
 Ezoi_XY |
100 | 0.313 s | 1.98 MiB | C++ |
 wangyucheng |
100 | 0.357 s | 4.51 MiB | C++ |
 evd |
100 | 0.404 s | 2.20 MiB | C++ |
 <蒟蒻>我要喝豆奶 |
100 | 0.690 s | 2.20 MiB | C++ |
|
evd |
80 | 0.403 s | 2.20 MiB | C++ |
|
wangyucheng |
10 | 0.368 s | 5.04 MiB | C++ |
|
wangyucheng |
10 | 0.387 s | 5.35 MiB | C++ |
|
<蒟蒻>我要喝豆奶 |
10 | 6.026 s | 2.32 MiB | C++ |
|
<蒟蒻>我要喝豆奶 |
10 | 6.028 s | 2.32 MiB | C++ |
|
wangyucheng |
10 | 9.002 s | 5.04 MiB | C++ |
| 关于 柠檬的坦克游戏 的近10条评论(全部评论) |
|---|
-
柠檬的坦克游戏
【题目背景】
『Citric杯』NOIP模拟赛 I 第二题
【题目描述】
Lemon最近迷上了一款坦克对战游戏。在这款游戏中，Lemon需要驾驶一辆坦克与敌军对战。坦克有很多不同的武器，每种武器有各自的特点，而Lemon所要做的就是合适地发射这些武器，对敌军造成最大的伤害。具体来说，每个武器都有两个参数：攻击力D和攻击半径R。为了简化题意，我们保证所有武器的攻击力D均不相同，所有武器的攻击半径R也均不相同。
Lemon决定对这些武器的性能进行评价。当然，评价不能只看攻击力D，也不能只看攻击半径R。Lemon觉得一件武器A优于另一件武器B，当且仅当A的攻击力大于B的攻击力且A的攻击半径大于B的攻击半径。
接下来，Lemon想要对武器进行分组，Lemon按照以下方式分组：
首先，我们定义f(A,S)为真当且仅当在武器集合S中的任何武器都不比武器A性能更优秀。
1.令i=0
2.令i=i+1 令S=还没被分组的武器集合
3.对于每一件S中的武器A，如果f(A,S)为真，则将武器A标记为第i组（注意S在这个过程中始终保持不变）
4.如果所有武器均被分组则结束，否则转2
给定N个武器的D和R，你的任务是按照Lemon的规则对这些武器进行分组。
【输入格式】
输入文件第一行包含一个正整数N，表示武器的个数。
接下来N行，每行两个正整数D，R，描述一件武器的攻击力和攻击半径。保证所有的D两两不同，所有的R两两不同。
【输出格式】
输出文件包含N行，每行一个正整数，第i行的数表示第i件武器被分在了哪一组。
【输入样例】
5
1 4
2 2
3 3
4 1
5 5
【输出样例】
2
3
2
2
1
【样例解释】
首先我们发现武器5比武器1性能更优，所以武器1不在第1组。同理武器2、3、4也不在第1组。但没有武器比武器5性能更优，因此武器5在第1组。
接下来还剩武器1、2、3、4没被分组。我们发现这些武器中没有武器比武器1更优，于是武器1在第2组，同理武器3、4也在第2组。
接下来只剩武器2了，武器2在第3组。
此时所有武器均被分组，过程结束。
【数据规模约定】
时间限制为1s
对于20%的数据，N<=100.
对于40%的数据，N<=3000.
对于100%的数据，N<=100000，1<=R,D<=10^9.