[关闭]
@zzzc18 2017-05-11T13:23:14.000000Z 字数 1346 阅读 551

2017.5.3 2

TEST


2. 柠檬的坦克游戏

( ( tank .pas/c/cpp)

【题目描述】

    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.

Solution

题目略长,不过仔细读之后也不是很难理解。

首先我们发现同一组内的武器,按 值从大到小排序后, 值必然也是从小到大的。

而且我们发现,如果一件武器 值比另一件武器 值大,那么武器 不会影响到武器 的分组。

于是考虑把武器按 值从大到小排序,然后逐个加入武器,并为新加入的武器找到合适的组。因为在新加入一件武器之前,我们已经加入了所有 值更大的武器,而剩下的武器都不会影响当前武器的分组,所以现在得出的组号就是最终的组号。

假设 值最大的前 个武器已经全部加入组,而且现在已经有 组了,定义第 组里最大的 值为 ,那么我们发现 必然随 递减。

我们考虑加入第 个武器,我们发现,按照题目要求,这件武器必然会加入到第 组,是最小的让 成立的 值。

于是我们直接用数组存储所有组的,新加入武器时二分查找到加入位置,然后更新对应的那个 即可。

时间复杂度

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注