algorithm - Hackerrank 上组织球容器问题的解决方案逻辑

Question

我正在解决这个问题，称为在 Hackerrank 上组织球容器：

大卫有几个容器，每个容器里都有许多球。他有足够的容器将他拥有的每种类型的球分类到自己的容器中。David 想使用他的排序方法对球进行排序。

例如，David 有n = 2 个容器和2种不同类型的球，它们的编号都是从0到n - 1 = 1。每个容器的球类型分布由一个nxn 整数矩阵描述M[container][type]。例如，考虑 `M = [[1,4],[2,3]] 的下图：

[...]

David 想要执行一些交换操作，例如：

• 每个容器只包含相同类型的球。
• 没有两个相同类型的球位于不同的容器中。

您必须执行q个查询，其中每个查询都采用矩阵M的形式。Possible对于每个查询，如果 David 可以满足上述给定矩阵的条件，则在新行上打印。否则，打印Impossible.

我尝试了各种解决方法，但找不到一种。然后我去了问题的讨论部分，我发现了这种方法 -

1. 制作一个盒子总数表（每个盒子的容量）
2. 制作球总数表（每种球类型的总数）
3. 对两个表进行排序
4. 如果它们相同，打印可能，否则打印不可能。

我试过了，它可以工作并通过所有测试用例。我只是不明白另一个用户提到的这个算法背后的逻辑。我只是希望有人帮助我解决这个问题的逻辑，更好的解决方案也会非常有益，因为我是这类问题的初学者。

我为此编写的代码是

def organizingContainers(container):
    print(container)
    
    countByType=[0]* len(container[0])
    countByContainer=[sum(x) for x in container]
    for Ci in container: 
        print ("Ci=", Ci)
        for j in range(len(Ci)):
            print(" j=",j)
            countByType[j]+=Ci[j]

    countByContainer.sort()
    countByType.sort()
    print('Count By Types:',countByType)
    print('Count By Container:',countByContainer)
    return "Possible" if countByContainer==countByType else "Impossible"

标签： algorithm

Answer 1

从对挑战的描述来看，容器可以具有不同的容量可能并不那么明显。给出的所有示例都有相同大小的容器。为了更好地理解问题，我发现使用具有不同大小容器的示例很有用：

         \ball types | red | blue | green
containers\          |     |      |    
---------------------+-----+------+-------
           A         |  2  |   3  |   1
           B         |  4  |   0  |   1
           C         |  1  |   3  |   3

所以我们有 3 个容器（命名为 A、B 和 C）和 3 种类型的球（红色、蓝色、绿色）。请注意，容器 B 是最小的：显然它可以包含 5 个球。A 可以包含 6 个球，C 可以包含 7 个球。

一个关键的观察结果是，如果我们首先清空容器，然后将球自由地分布在容器上，再次填充它们，总有一种方法可以通过简单的交换来实现相同的过渡。您可能需要一点时间来了解这一点并验证情况确实如此。但是一旦你掌握了这个原则，你就可以忘记交换部分，并从你首先移除所有球然后再次分配它们的角度来解决问题。

所以让我们清空容器。然后，我们“手中”有以下球：

 red | blue | green
-----+------+-------
  7  |   6  |   5

现在问自己：如果容器 B 的容量为 5，你会在里面放哪种球？显然是绿球。它不适用于任何其他类型的球，因为您必须将其中一个或多个放在另一个容器中，这违反了要求。

因此，一般规则是：将您拥有的球最少的球放入容量最小的容器中。如果球的数量与容量不匹配，那么就没有办法解决。如果匹配，那么您可以对下一种球（按递增顺序）和下一个容器（按容量递增）重复此操作。所以你看到像这样对容器和球进行分类是一种找到解决方案的方法。