Есть интересная задача, которая звучит так:
Для каждой из N книг (N - натуральное число) дается порядковый номер от 0 до N-1. Затем для каждой книги вводится число pi такое, что |pi| – число страниц в i-ой книге. Сами pi могут быть отрицательными. Далее каждой книге ставится в соответствие число X: Xi=∑j |pi−pj| (т.е. сумму разностей количества страниц (с учётом знака при pi) i-ой книги со всеми остальными книгами). Потом все книги выставляют в порядке возрастания величины Xi. Если у нескольких книг величина X совпадает, первой берётся та книга, порядковый номер которой меньше.
Формат входных данных
В первой строке дано целое число N – количество книг (0≤N≤10^5).
В следующей строке содержится N целых чисел pi – количество страниц в каждой из книг по порядку (|pi| ≤ 10^6).
Формат выходных данных
В единственной строке выведите N чисел – номера книг в том порядке, в котором они должны быть упорядочены.
Пример:
Input:
5
0 1 2 3 4
Output:
3 2 4 1 5
Я уже придумал решение, но в нем есть 'минус' - слишком большое время работы. Хотелось бы его сократить. Ниже привожу решение с пояснениями:
from math import fabs as f # здесь импортируем модуль
N = int(input()) # Принимаем ненужное число
P = input().split()
P = [int(i) for i in P] # Создаем список из данных чисел pi для каждой книги
P_copy = P.copy() # Нужна копия для удобного использования
X_books = [] # Здесь хранятся Xi переменные для каждой книги
for i_0 in P:
X = 0
P_copy = P.copy() # каждый раз в цикле нужна "свежая" копия
index = P_copy.index(i_0)
del P_copy[index] # удаляем из копии соответствующий элемент, чтобы потом найти X
for i_1 in P_copy: # путем суммирования модулей разностей с остальными элементами Xi=∑j |pi−pj|
X += f(i_0 - i_1)
X_books.append(X) # собираем наш массив из соответствующих 'иксов'
X_books_copy = X_books.copy() # нам необходима копия, чтобы не терять индексы
X_books_copy = sorted(X_books_copy) # Т. е. сначала мы расставляем копию в порядке возрастания
M = max(X_books_copy) # затем перебираем в ней элементы и берем соответсующие индексы "из оригинала"
for i in X_books_copy: # на место прошедшего элемента в оригинале заменяем его на такой элемент,
index = X_books.index(i) # который в копии никогда не встретится
del X_books[index] # например, максимальный + 1 (M+1)
X_books.insert(index, M+1)
print (index+1, end = ' ')
В приведенном ранее примере X_books = [10.0, 7.0, 6.0, 7.0, 10.0] (до того, как создан X_books_copy)
