8

Here is the question (link: 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.

I came up with this code:

#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;
}

It is working fine and giving correct answer for 70% of the test cases but crosses the time limit for the remaining. Is there any other, faster algorithm to solve this question?

4

4 回答 4

7

您的算法具有复杂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，定义S(X) = M[1] + M[2] + ... + M[X]。S被称为前缀总和。F(K)等于N加减如此1低。每次我们将数字放置到位置时，我们都会将 0 放置到. 为了更快地找到，我可以建议使用二叉索引树来及时计算前缀总和，并使用二叉​​搜索来找到等于某个预定义值的值。XS(X) = KZN + 1 - X(for K = I[Z] + 1)M[X]XO(N)O(logN)XS(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。我还可以建议您阅读一些有关算法和奥林匹克竞赛的书籍，例如 Skienna（编程挑战）或 Cormen（算法简介）

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

于 2012-10-27T09:07:10.947 回答
3

最昂贵的部分显然是在结果数组中移动多达 100 000 个元素。

如果将该数组拆分为更多块，则可以通过一些重要因素加快它的速度。

如果您有 10 个块并记住每个块的元素数量，则您可以根据键选择要写入的正确块，然后必须仅移动该块的元素（最多减少 10 倍）。

新的问题是如何在块中实现良好的数字分布。

您也可以使用链接列表：http ://www.cplusplus.com/reference/stl/list/

它在插入时非常有效，但对于随机搜索却很糟糕。但仍然寻找只是读取操作，因此寻找 x 元素可能比在数组中移动 x 元素更快（IDK）。

然后您可以使用组合方法并使用带有多个指针的链表，因此您始终可以从最近的指针中查找。

于 2012-10-27T09:00:21.340 回答
2

这是一个非常好的算法以及所需的 C++ 编码：

问题是这样解决的7 _ _ _ _。

现在，平方根分解完成，插入完成：

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int n, k = 0, d, r, s, sum, temp, m, diff, check = 1;
    cin >> n;

    d = sqrt(n) + 1;
    int arr[n], result[n], indices[d], arr2[d][d], num = 1;

    for (int i = 0; i < n; i++)
        cin >> arr[i];               //The inversion sequence is accepted.

    for (int i = 0; i < d; i++)
        indices[i] = 0;              //Indices tell where to start counting from in each row.

    for (r = 0; r < d; r++)
    {
        for (s = 0; s < d; s++)
        {
            arr2[r][s] = num;       //Array is filled with 1 to n (after sqrt decomposition).
            num = num + 1;
            if (num == n+1)
            {
                check = 0; break;
            }
        }
        if (check == 0)
            break;
    }

    int l = s;
    while (l >= 0)                  //Non-Zero numbers are shifted to right and 0 placed in
    {                               //empty spaces.
        arr2[r][d-1 - k] = arr2[r][l];
        k = k + 1; l = l - 1;
    }

    k = d-1 - k + 1;
    for (int t = 0; t < k; t++)
        arr2[r][t] = 0;

    indices[r] = indices[r] + k;    //Index of the last row is shifted to first non-zero no.

    for (int i = n-1; i >= 0; i--)
    {
        sum = 0; m = 0;
        while (sum < arr[i] + 1)
        {
            sum = sum + (d - indices[m]); //Empty boxes in each row are counted.
            m = m + 1;
        }

        m = m - 1;
        sum = sum - (d - indices[m]);     //When sum = 1 + corresponding value in inversion
        diff = arr[i] + 1 - sum;          //sequence, then that particular value is made 0
        temp = indices[m] + diff - 1;     //and (that value - 1) is the index of the number
                                      //to be placed in result array.
        result[arr2[m][temp] - 1] = i+1;
        for (int w = temp - 1; w >= indices[m]; w--)
        {
            arr2[m][w + 1] = arr2[m][w];  //Then, 0 is shifted to just before non-zero number
        }                                 //in the row, and the elements are shifted right
        arr2[m][indices[m]] = 0;          //to complete the sort.
        indices[m] = indices[m] + 1;
    }                                     //This is done n times for 1 to n integers thus
                                      //giving the permutation in reverse order in result
    for (int p = n-1; p >= 0; p--)        //array.
        cout << result[p] << ' ';

    return 0;
}
于 2012-11-25T11:52:42.097 回答
1

您的算法对这个问题效率不高，因为您的复杂度是 O(n^2)，这意味着对于某些输入情况需要 10^10 次操作。你必须想出一个更便宜的解决方案。

我建议您使用以下算法（从 1 到 N 的索引）：

for i=1 to N
   input a(i)
   if i==1 insert 1 into b
   else insert i into b at place i-a(i)
end
于 2012-10-27T09:13:20.593 回答