algorithm - 用立方体 build 一座塔

您可以通过不将较大的立方体放入较小的立方体来使用立方体制作稳定的塔，并且您不能将较重的立方体放入较轻的立方体中。

编写一个程序，用 N 个立方体给出最高的塔。

输入 txt 的第一行包含立方体的数量。 (1
例子:

Input.txt       Output.txt (from bottom to top)
5               3
10 3            20 5
20 5            10 3
15 6            10 2
15 1
10 2

内存限制:16 mb 运行时间:0.2 秒

你能帮助我吗？

最佳答案

算法

我想出的算法通过使用有序对列表来工作。这些对首先按一个元素排序，然后按第二个元素排序。

我们维护对列表，其中每个新对是:

添加到最高列表的末尾，如果它可以放在最后一个元素之后

添加到新列表的末尾，这是在现有列表之一中找到的最高段的副本，可以将其附加到

如果

不能放入现有列表中的任何位置，则将其添加到新列表中。

证明

第一个元素将进入一个新列表，然后是最高的。

n -th 元素将转到最高列表(或列表段)的末尾，使其成为具有该元素的最高列表。

n 之后的第一个元素，元素 k ，可以附加到带有 的列表中 n 将附加到包含 n 的最高列表中，因为如果存在更高的列表 2，则存在一些更高的元素i 可以附加元素 k ，然后将规则 2 应用于元素 i 。这使得带有 k 的列表成为具有该元素的最高列表。

通过归纳，这证明了算法的概念。

伪代码

foreach ordered pair
    maximumIndex <- 0
    maximumList <- null
    foreach list
        highest, length <- FindLongestPath(list, pair)
        if highest > maximumHeight
            maximumHeight<- highest
            maximumIndex <- lenght
            maximumList <- list
    if maximumIndex = 0
        lists.add(new list{pair});
    else if maximumIndex < maximumList.Length
        lists.add(new list{maximumList[0..maximumIndex - 1] + pair});
    else
        list.add{pair};

FindLongestPath 方法在列表中搜索该对可以容纳的第一个位置，并返回该段的高度。通过一个简单的应用程序(从开始到找到位置的 for)，我估计算法的复杂度在最坏的情况下为 O(N^2)。

如果实现为二分搜索，我猜复杂度将是 O(N log N)，但对于 N
实际代码

由于没有人喜欢破译其他人的伪代码，这里是 pastebin 上实际工作的 C# 代码:http://pastebin.com/3vLn343j

文件“Input.txt”的格式与问题一样，应该与可执行文件位于同一目录中(在 Visual Studio 中，您可以将它放在解决方案根目录中，并在属性中将“复制到输出”设置为“如果更新则复制” ')。

关于algorithm - 用立方体 build 一座塔，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20020051/