4

Условие задачи:

По заданной перестановке требуется определить обратную.

Перестановкой из 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 действий. По факту, я очень сомневаюсь насчет своей реализации и мне очень даже кажется, что здесь можно реализовать все гораздо проще.

  1. Даже если идея моего решение и неверна (в плане эффективности), эффективно ли я реализовал свою идею?

  2. Можно ли придумать что-то получше?

2 ответа 2

4

Да не нужны тут два массива... Просто сразу собираем массив для вывода, не сохраняя ввод.

#include <iostream>
int i,N,a,b[20002];
main()
{
    std::cin>>N;
    for(;std::cin>>a;b[N-a]=++i);
    for(;N--;) std::cout << b[N] << " ";
}

Если не очень понятно - ну, так это acmp, они краткость хотят... :)

3

Начнём с того, что ваша программа работает очень плохо, потому как 4*10^8 степени - это слишком большая роскошь, и за одну секунду очень вряд ли она успеет сработать. А тут всё просто. В этой задаче нам нужно сделать так, что бы при обратной перестановке значение возвращалось к начальному. Для решения задачи нам нужно понять, что эта операция - это перенос значения из позиции i в позицию Mas[i]. А это значит, что в обратной перестановке значение из позиции Mas[i] переходит в i. То есть, что бы эти значения были одинаковы, нам просто нужно, что бы в нашем ответе на Mas[i] позиции стояло значение i. Реализуется очень просто:

#include <bits/stdc++.h>
using namespace std;


int main()
{
 int n;
cin >> n;
vector<int>Mas(n + 1);
vector<int>Res(n + 1);
for (int i = 1; i <= n; i++) {
    cin >> Mas[i]; //считываем массив 
}

for (int i = 1; i <= n; i++) {
    Res[Mas[i] ] = i ; //Присваиваем каждому Mas[i] элементу значение i
}

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.