java - 大猩猩和波兰人会面点算法 - 无法找出完美的解决方案和失败的测试用例

问题描述

我在一个有竞争力的编码网站上练习时遇到了这个问题。经过深思熟虑，我提出了下面提到的逻辑，但不知何故，我无法通过大多数测试用例。此外，该网站没有公开测试用例，所以我对可能出现的问题一无所知。问题描述如下：

问题陈述

一群大猩猩正在马戏团中表演，并被放置在多个杆子上。两极的底座浸入水中。您将获得二维平面中所有极点的 x 和 y 坐标。由于大猩猩不会游泳，它们从一根杆子移动到另一根杆子的唯一方法就是跳跃。然而，当一只大猩猩从一根杆子跳到另一根杆子时，他跳的杆子会被淹没更深 1 个单位。请注意，只有被跳跃的杆子才会被淹没。跳到的杆子不受影响。对于马戏团的高潮，所有大猩猩必须在一根杆子上相遇。所有大猩猩的跳跃能力，即“J”给你。跳跃能力无非就是一只大猩猩一次跳跃所能走的距离。只有当A和B之间的几何距离小于或等于“J”即跳跃能力时，大猩猩才能从A极跳到B极。每根柱子都有一个给定的水面高度，所以固定数量的大猩猩可以从每根柱子上跳下来，之后它会被淹没。如果极点的编号是从 0 到 N-1，则需要确定所有大猩猩在马戏团高潮期间有可能相遇的极点。假设大猩猩可以在 4 个极点中的所有极点相遇，则打印 0 1 2 3。如果它们只能在 0 和 4 极点相遇，则打印 0 4。如果它们不能在任何极点相遇，则打印 -1。大猩猩可以进行任意数量的跳跃，只要按照上述条件是可能的。之后它会被淹没。如果极点的编号是从 0 到 N-1，则需要确定所有大猩猩在马戏团高潮期间有可能相遇的极点。假设大猩猩可以在 4 个极点中的所有极点相遇，则打印 0 1 2 3。如果它们只能在 0 和 4 极点相遇，则打印 0 4。如果它们不能在任何极点相遇，则打印 -1。大猩猩可以进行任意数量的跳跃，只要按照上述条件是可能的。之后它会被淹没。如果极点的编号是从 0 到 N-1，则需要确定所有大猩猩在马戏团高潮期间有可能相遇的极点。假设大猩猩可以在 4 个极点中的所有极点相遇，则打印 0 1 2 3。如果它们只能在 0 和 4 极点相遇，则打印 0 4。如果它们不能在任何极点相遇，则打印 -1。大猩猩可以进行任意数量的跳跃，只要按照上述条件是可能的。

输入

第一行是一个整数 N，表示极数。
第二行是一个小数 J，表示所有大猩猩的跳跃能力。

连续的 N 行包括：
xi = 极点的 x 坐标，yi = 极点的 y 坐标，gi = 极点上大猩猩的初始数量，hi = 极点最初高于水面的高度。

输出

打印大猩猩可能相遇的两极的序列号。如果他们不可能在任何地方见面，请打印 -1。

约束

1 <= N <= 100

0 <= J <= 100000

-10000 <= xi, yi <= 10000

0 <= gi <= 25

1 <= 嗨 <= 200

示例测试用例

输入

3 30.0
1 10 5 20
5 10 5 20
8 10 5 20

输出

0 1 2

解释

所有杆之间的距离 < 30.0，因此所有大猩猩在距离方面都可以从任何杆跳到任何其他杆。此外，所有极点的高度，即 20 > 没有。每根杆上都有大猩猩，因此大猩猩可以通过直接跳上它们轻松地在 0、1 或 2 杆上相遇。

方法

让我们将所有给定的信息存储在一个二维整数数组中。

// 4 columns to store xi, yi, gi and hi for each given pole.
int [][] polesInfo = new int[N][4];

首先，我们需要一个循环来逐个遍历所有极点，并查看来自所有极点的大猩猩是否可以跳到我们正在查看的一个极点上。

boolean [][] result = new boolean[N];
for(int i = 0; i < N; i++) {
    result[i] = canAllGorillasJumpToI(polesInfo,i)
}

在canAllGorillasJumpToI()方法里面，我基于3个案例实现了，

所有大猩猩都可以直接跳到极点，即所有极点都有足够的高度，并且所有极点的距离都小于 J。因此，就像给定的测试用例一样，可以从所有极点直接跳，我们返回 true。
其中一根杆子的大猩猩数量超过了它的高度，不可能所有的大猩猩都跳到它的任何地方，因此最终会留下一些大猩猩，在这种情况下，所有的大猩猩都永远不会在第i杆相遇，因此返回错误的。
这是我遇到的最复杂的情况，我怀疑它遗漏了一些东西。如果某些大猩猩由于杆子距离较远而无法直接跳跃，请检查其他有足够能力的杆子跳跃，然后尽可能连续跳跃到目标杆子。

1和2很简单。但这是我对 3 的逻辑。

将所有大猩猩无法直接跳跃的所有极点存储在 ArrayList 中。总结需要进行间接跳跃的大猩猩数量。

for (Integer p : poles) {
    gorillaPositions += polesInfo [p][2];
}

找出目标极点附近的所有极点，即距离小于 J 的极点。存储它们可用的剩余容量的总和。

//pseudocode
if (poles in vicinity) {
    capacity += polesInfo [i][3] - polesInfo [i][2];
}

最后，我正在检查 gorilla posiitons >= capacity 并返回 true。

if (gorillaPositions >= capacity ) {
    return true;
}

这种逻辑似乎在某些情况下有效，但在大多数测试用例中都失败了。我知道在案例 3 中有些地方不对劲，而且我无法想到这种情况。

什么是更好的算法来做到这一点？我应该使用图表吗？任何帮助或测试用例将不胜感激。如有必要，我可以分享更多细节或测试用例。

标签： javaalgorithmdata-structures

java - 大猩猩和波兰人会面点算法 - 无法找出完美的解决方案和失败的测试用例

问题描述

解决方案

推荐阅读