c++ - 我需要一个更好的算法来解决这个问题

Question

这是问题(链接:http://opc.iarcs.org.in/index.php/problems/FINDPERM):

A permutation of the numbers 1, ..., N is a rearrangment of these numbers. For example
2 4 5 1 7 6 3 8
is a permutation of 1,2, ..., 8. Of course,
1 2 3 4 5 6 7 8
is also a permutation of 1, 2, ..., 8.
Associated with each permutation of N is a special sequence of positive integers of length N called its inversion sequence. The ith element of this sequence is the number of numbers j that are strictly less than i and appear to the right of i in this permutation. For the permutation
2 4 5 1 7 6 3 8
the inversion sequence is
0 1 0 2 2 1 2 0
The 2nd element is 1 because 1 is strictly less than 2 and it appears to the right of 2 in this permutation. Similarly, the 5th element is 2 since 1 and 3 are strictly less than 5 but appear to the right of 5 in this permutation and so on.
As another example, the inversion sequence of the permutation
8 7 6 5 4 3 2 1
is
0 1 2 3 4 5 6 7
In this problem, you will be given the inversion sequence of some permutation. Your task is to reconstruct the permutation from this sequence.

我想出了这段代码:

#include <iostream>

using namespace std;

void insert(int key, int *array, int value , int size){
    int i = 0;
    for(i = 0; i < key; i++){
        int j = size - i;
        array[ j ] = array[ j - 1 ];
    }
    array[ size - i ] = value;
}

int main(){

    int n;
    cin >> n;
    int array[ n ];
    int key;

    for( int i = 0; i < n; i++ ){
        cin >> key;
        insert( key, array, i + 1, i);
    }

    for(int i = 0;i < n;i ++){
        cout << array[i] << " ";
    }

return 0;
} 

它工作正常并为 70% 的测试用例给出了正确答案，但超过了剩余测试用例的时间限制。有没有其他更快的算法来解决这个问题？

Answer 1

您的算法具有复杂的 O(N^2) 操作，因此对于大小为 10^5 的数组，它需要太多时间来执行。我尝试描述更好的解决方案:

我们有 N 个数字。让我们调用逆数组 I。解决这个问题我们需要知道从排列结束的 K-th 位置在哪里，它仍然是空闲的(我们称这个函数为 F(K))。首先，我们把数字N放到位置F(I[N] + 1)，然后把数字N-1放到位置 F(I[N-1] + 1) 等等。

F 可以按如下方式计算:声明大小为 N 的数组 M:1 1 1 ... 1，定义S(X) = M[1] + M[2] + ... + M[X]。 S 被称为前缀和。 F(K) 等于 N 加上 1 减去 X 即 S(X) = K。每次我们将数字 Z 置于 N + 1 - X(对于 K = I[Z] + 1) 时，我们将零置于 M[X]。要在 O(N) 时间内更快地找到 X，我建议使用 Binary Indexed Trees在 O(logN) 时间内计算前缀和，Binary Search找到 X 使 S(X) 等于某个预定义的值。

这种算法的总复杂度是 O(N(log(N))^2)。 This isRuby 中的实现(您可以直接在 ideone 中使用它:更改输入、运行并检查输出):

# O(n(log(n))^2) solution for http://opc.iarcs.org.in/index.php/problems/FINDPERM

# Binary Indexed Tree (by Peter Fenwick)
# http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
class FenwickTree

  # Initialize array 1..n with 0s
  def initialize(n)
    @n = n
    @m = [0] * (n + 1)
  end

  # Add value v to cell i
  def add(i, v)
    while i <= @n
      @m[i] += v
      i += i & -i
    end
  end

  # Get sum on 1..i
  def sum(i)
    s = 0
    while i > 0
      s += @m[i]
      i -= i & -i
    end
    s
  end

  # Array size
  def n
    return @n
  end

end

# Classical binary search
# http://en.wikipedia.org/wiki/Binary_search_algorithm
class BinarySearch

  # Find lower index i such that ft.sum(i) == s
  def self.lower_bound(ft, s)
    l, r = 1, ft.n
    while l < r
      c = (l + r) / 2
      if ft.sum(c) < s
        l = c + 1
      else
        r = c
      end
    end
    l
  end

end

# Read input data
n = gets.to_i
q = gets.split.map &:to_i

# Initialize Fenwick tree
ft = FenwickTree.new(n)
1.upto(n) do |i|
  ft.add i, 1
end

# Find the answer
ans = [0] * n
(n - 1).downto(0) do |i|
  k = BinarySearch.lower_bound(ft, q[i] + 1)
  ans[n - k] = i + 1
  ft.add k, -1
end
puts ans.join(' ')

O(N(log(N))) 时间的解决方案也存在。它使用某种 Binary Search Tree :我们用顶点上的数字 1, 2, 3, ... N 创建 BST，然后我们可以在 O(log (N)) 并在 O(log(N)) 时间内删除顶点。

还有 std::set 的解决方案可能存在，但我现在想不到。

附言。我还可以建议您阅读一些关于算法和 olimpyads 的书籍，例如 Skienna(编程挑战)或 Cormen(算法导论)

PPS.很抱歉我之前描述的错误解决方案