Вот вопрос (ссылка: 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-й элемент этой последовательности — это количество чисел j, строго меньших i и стоящих справа от i в этой перестановке. Для перестановки
2 4 5 1 7 6 3 8
последовательность инверсии
0 1 0 2 2 1 2 0
2-й элемент равен 1, потому что 1 строго меньше, чем 2, и он появляется справа от 2 в этой перестановке. Точно так же 5-й элемент равен 2, поскольку 1 и 3 строго меньше 5, но появляются справа от 5 в этой перестановке и т. д.
Другой пример: последовательность инверсии перестановки
8 7 6 5 4 3 2 1
is
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% тестовых случаев, но превышает лимит времени для остальных. Есть ли другой, более быстрый алгоритм для решения этого вопроса?
