@William03

Как сократить время выполнения данной программы — не более 1 секунды (Python)?

Есть интересная задача, которая звучит так:
Для каждой из 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)
  • Вопрос задан
  • 296 просмотров
Решения вопроса 1
longclaps
@longclaps
n = w = int(input())
pp = list(map(int, input().split()))
s = sum(pp)
for i in sorted(range(n), key=pp.__getitem__):
    p = pp[i]
    pp[i] = s - w * p
    w -= 2
    s -= p * 2
print(*[i + 1 for i in sorted(range(n), key=pp.__getitem__)])
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы