我得到了一个由n个不同整数a0，a1，…组成的序列，。。。a(n−1(。在每次迭代中，我选择最大数量并将其删除；删除最大数字的成本是它左边的数字数量。重复此操作n次。我必须找到n次迭代的总成本。
例如，如果A[]=｛6，2，8，4，9，3｝
总成本为：4+2+0+1+1+0=8
我知道有O(n-logn(算法可以解决这个问题，常见的是合并排序方法和BST方法。
但我对如何实施BST方法感到困惑。如有任何关于如何开始的帮助，我们将不胜感激。
但我对如何实现BST方法感到困惑。
如果您编写一个平衡的二进制搜索树实现(如红黑树实现(，并让它跟踪每个节点子树的大小(您可以在不影响渐近复杂性保证的情况下这样做(，那么您可以给它一个"index of"或"count less than"方法，该方法在O(logn(时间内计算有多少元素小于给定值。
创建该实现是困难的部分(尽管至少您不需要支持删除(；一旦你有了它，算法就非常简单：
- 初始化一个树，最初为空
- 初始化一个整数结果，最初为零
- 对于每个元素elem：
- 询问树有多少元素小于elem；将该数字添加到结果
- 将elem添加到树中
- 返回结果
TLDR:
您正在查找用于降序排序的数组中的反转数。这在O(n lg n)中是可行的。
数组A中的反转数定义为所有索引对i、j的数目，使得i < j和A[i] > A[j]。因此，基本上是A中值对的数量，如果对A进行排序，则第一个值将出现在第二个值之后。这可以通过遍历A中的所有值并计算之前应该出现的值来计算：
count_inversions(A):
count = 0
for i=0 to length of A - 1:
for j=0 to i - 1:
if A[i] > A[j]:
count++
return count
对于你的问题，天真的解决方案将非常相似：
total_delete_cost(A):
count = 0
for i=0 to length of A - 1:
for j=0 to i - 1:
if A[i] < A[j]:
count++
return count
唯一改变的是线路if A[i] > A[j]。或者换一种方式来看：A中的每个值x都会将m添加到总成本中，其中m是大于x且具有更高索引的值的数量。这正是来自CCD_ 16的反向排序的反转次数。
从这里开始，除了从升序切换到降序的小调整外，问题的其余部分都在这里得到了回答，所以我不会发布代码来解决问题的剩余部分。