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

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

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

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

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

假设 $D$ 值最大的前 $x$ 个武器已经全部加入组，而且现在已经有 $k$ 组了，定义第 $i$ 组里最大的 $R$ 值为 $maxR(i)$，那么我们发现 $maxR(i)$必然随 $i$ 递减。

我们考虑加入第 $x+1$个武器，我们发现，按照题目要求，这件武器必然会加入到第 $i$ 组，$i$是最小的让 $maxR(i)<R$ 成立的 $i$ 值。

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

时间复杂度 $O(nlog(n))$