逐个删除最小节点后找出总成本

Question

给定n个不同的整数a，a1，a2，...，an-1的序列。在每次迭代中，你选择最小的数字并删除它，删除最小数字的成本是它右边的数字的数量。重复此操作n次。给出了计算n次迭代总代价的ai实现O( Given )算法。

例如: A[] = 6,2,8,4,9,3

cost == 4+0+1+2+1+0 = 8；

我知道我必须在这里使用BST，但我不能得到删除节点后如何获得成本的想法。

Answer 1

注意，一个元素的成本恰好是该元素右侧大于它的元素的数量。您可以维护std::set并从右向左扫描阵列。每次遇到元素时，使用std::set计算其成本，然后将此元素添加到std::set。这是一个O(n log n)算法。

Answer 2

我知道我必须在这里使用BST

不一定(除非任务明确要求)：

你可以提前在O(n log n)中按降序对数组进行排序(例如，像std::sort那样使用intro sort )，然后一次删除所有元素的开销是O(1)，假设只需将结束指针移动到数组中(例如，使用std::vector，它在内部这样做)-或者如果需要将剩余的值复制到新的数组中，则可能使用n - r r要删除的元素的数量。

如果你依赖原始的顺序，你可以用它的原始索引来标记每个值(例如std::vector<std::pair<unsigned long, size_t>>)，并通过再次对索引进行排序来恢复顺序，同样是O(n log n) (实际上甚至更少，因为我们这里有一个简化的n ...)。如果需要就地修改原始数组，则可以添加另一个仅具有索引的数组，并且在排序时并行执行两个数组上的所有操作。

总而言之，你会得到：

O(n log n + (either n - r or 1) + (n - r) log (n - r)) = O(n log n)

使用r <= n要删除的元素的数量。