Условие задачи:
По заданной перестановке требуется определить обратную.
Перестановкой из N элементов называется упорядоченный набор из N различных чисел от 1 до N. Количество различных перестановок порядка N равно PN = N!
Пусть у нас есть упорядоченное множество из N элементов. Перестановка задает преобразование этого множества. А именно, она говорит, что на i место нужно поставить ai элемент множества, где ai - i-тый элемент перестановки.
Обратной перестановкой к перестановке π называется такая перестановка π-1, что ππ-1 = π-1π = ε, где ε – тождественная перестановка. То есть если применить сначала перестановку π, а потом обратную к ней π-1, то в итоге получится такой результат, как если бы мы эти перестановки не применяли вообще. Такой же результат получится, если сначала применить обратную перестановку π-1, а потом прямую π.
Входные данные В первой строке входного файла INPUT.TXT записано число 0 < N ≤ 20000 - порядок перестановки. Во второй строке записана сама перестановка.
Выходные данные В выходной файл OUTPUT.TXT выведите обратную перестановку.
Вкратце поясню что от нас хотят.
[5,7,4] - массив
(2,1,3) - перестановка
[7,5,4] - результат
(2,1,3) - обратная перестановка (обратная перестановка не всегда равна перестановке)
[5,7,4] - результат. (мы вернулись к исходному массиву, что и нужно было)
Ответ: (2,1,3)
Допустим у нас есть массив a - [5,7,4]
и есть его перестановка (2,1,3)
. Это значит, что в первую ячейку массива я ставлю второй элемент. То есть a[0] = 7
. На вторую - первый a[1] = 5
. На третью - третий a[2] = 4
. Но нам же требуется найти обратную перестановку. Значит нужно найти такую перестановку которая вернет к исходному массиву.
Идея моего решения:
Массив чисел можно сразу представить как последовательность натуральных чисел с 1 до n. То есть, например, массив у меня есть перестановка (2, 3, 4, 1)
и массив [1,2,3,4]
. Итоговый результат и будет этой перестановкой - [2,3,4,1]
. Значит надо из перестановки (2,3,4,1)
сделать возрастающую перестановку - (1,2,3,4)
, отсюда уже идея решения.
Ищем минимальные числа по порядку и выводим их индексы (нумерация с 1).
Код решения:
#include <bits/stdc++.h>
using namespace std;
bool used[20001]; //записываем минимумы которые уже использовались
int main()
{
int n;
cin >> n;
vector<int> a(n);
for (auto& b : a)
cin >> b;
for (size_t i = 0; i < n; i++)
{
int min = 20001;
int mini = -1;
for (size_t j = 0; j < n; j++)
{
if (min > a[j] && !used[a[j]]) //поиск неиспользованного минимума
{
min = a[j];
mini = j;
}
}
used[min] = true; //использованный минимум больше не трогаем
cout << mini + 1 << " ";
}
}
На тестах пишет, что время на тесты у моей программы вышло. Хотя это неудивительно. Асимптотика O(n^2) ~ 4*10^8 действий. По факту, я очень сомневаюсь насчет своей реализации и мне очень даже кажется, что здесь можно реализовать все гораздо проще.
Даже если идея моего решение и неверна (в плане эффективности), эффективно ли я реализовал свою идею?
Можно ли придумать что-то получше?