请帮助我理解这一礼貌测试。

Question

考虑到下面的礼貌测试：

给定一个A的N整数数组，我们在二维平面上绘制N盘，使得I-th盘以(0,I)为中心，半径为A[I]。我们认为，KandJ-th andK-th discs have at least one common point. Write a functionclass解{公共整数解(int[] A)；}that, given an arrayAdescribingNdiscs as explained above, returns the number of pairs of intersecting discs. For example, givenN=6and:A =1 A1 =5 A2 = 2A3 =1 A4 =4 A5 = 0Intersecting discs appear in **eleven pairs of elements**: 0 and 1, 0 and 2, 0 and 4, 1 and 2, 1 and 3, 1 and 4, 1 and 5, 2 and 3, 2 and 4, 3 and 4, 4 and 5. so the function should return11. The function should return−1if the number of intersecting pairs exceeds 10,000,000. Assume that: -Nis an integer within the range0..100,000`;

• 数组A的每个元素都是范围0..2147483647.Complexity内的整数

• 最坏时间复杂度为O(N*log(N))；
• 最坏情况下的空间复杂度是O(N)，超出了输入存储(不包括输入参数所需的存储)。

这十一对是从哪里来的，因为只有六个元素？

Answer 1

只有6个元素，但可能的对数是6*5/2=15 (一般形式：n(n-1)/2))，因此即使有6个点，也可能有多达15个(包括)交叉口，如上所述。

磁盘的数量不是最大的15个，因为一些“磁盘”不相交，例如，磁盘(0,0)和磁盘(0,5)没有公共点。(0,0)包括点{(0,0), (0,1)}，(0,5)磁盘包括点{ (0,5) }。

因为这两个集合的交集是空的-- (0,0);(0,5)不是有效的磁盘对，不应该包括在内。

Answer 2

这11对和问题中所列的一模一样。每个光盘都以(0, I)为中心，因此每个光盘与其两个相邻的每个都是一个距离单位(磁盘0和磁盘N1除外，它们只有一个邻接)。对于给定的特定数组A：

• 盘0的半径为1，因此它与盘1相交。
• 圆盘1的半径为5，所以它与圆盘0，2，3，4，5相交。
• 圆盘2的半径为2，所以它与圆盘0，1，3，4相交。
• 圆盘3的半径为1，因此它与圆盘2，4相交。
• 圆盘4的半径为4，所以它与圆盘0，1，2，3，5相交。
• 盘5的半径为0，因此它与无盘相交。

如果您只计算此列表中的唯一对(例如，2与3相交，3相交与2相交，即1)，则为11个交叉口。