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

Question

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

数字1,...,N的排列是这些数字的重新排列.例如,
2 4 5 1 7 6 3 8
是1,2,...,8的置换.当然,
1 2 3 4 5 6 7 8
也是1,2,...,8的置换.
与N的每个排列相关联的是长度为N的正整数的特殊序列,称为其反转序列.该序列的第i个元素是严格小于i的数字j的数量,并且在该排列中出现在i的右侧.对于置换
2 4 5 1 7 6 3 8
,反转序列是
0 1 0 2 2 1 2 0
第二个元素是1,因为1严格小于2,在这个排列中它出现在2的右边.类似地,第5个元素是2,因为1和3严格小于5但在此排列中出现在5的右侧,依此类推.
作为另一个例子,置换的反转序列
8 7 6 5 4 3 2 1
是
0 1 2 3 4 5 6 7
在这个问题中,你将得到一些置换的反演序列.您的任务是从此序列重建置换.

我想出了这段代码:

#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可以如下计算:声明M大小的数组N:1 1 1 ... 1,define S(X) = M[1] + M[2] + ... + M[X].S被称为前缀和.F(K)等于N加1减去这样低X的是S(X) = K.每次我们把数字Z放到位置N + 1 - X(for K = I[Z] + 1)我们把零放到M[X].为了找到X更快然后在O(N)时间我可以建议使用二进制索引树来计算前缀款项O(logN)的时间,二进制搜索找到这样X说S(X)等于某个预定义值.

这种算法的总复杂性是O(N(log(N))^2).这是 Ruby中的实现(你可以在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)))时间的解决方案也存在.它使用某种二元搜索树:我们1, 2, 3, ... N在椎体上创建带有数字的BST ,然后我们可以在数值上找到K-th数字O(log(N))并O(log(N))及时删除椎体.

还有std :: set的解决方案可能存在,但我现在想不到一个.

PS.我还建议你阅读一些关于algo和olimpyads的书籍,如Skienna(编程挑战)或Cormen(算法导论)

PPS.对不起我之前描述的错误解决方案