@zzzc18
2017-05-11T21:23:14.000000Z
字数 1346
阅读 1454
TEST
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.
题目略长,不过仔细读之后也不是很难理解。
首先我们发现同一组内的武器,按 值从大到小排序后, 值必然也是从小到大的。
而且我们发现,如果一件武器 的 值比另一件武器 的 值大,那么武器 不会影响到武器 的分组。
于是考虑把武器按 值从大到小排序,然后逐个加入武器,并为新加入的武器找到合适的组。因为在新加入一件武器之前,我们已经加入了所有 值更大的武器,而剩下的武器都不会影响当前武器的分组,所以现在得出的组号就是最终的组号。
假设 值最大的前 个武器已经全部加入组,而且现在已经有 组了,定义第 组里最大的 值为 ,那么我们发现 必然随 递减。
我们考虑加入第 个武器,我们发现,按照题目要求,这件武器必然会加入到第 组,是最小的让 成立的 值。
于是我们直接用数组存储所有组的,新加入武器时二分查找到加入位置,然后更新对应的那个 即可。
时间复杂度