Офісна Вулиця. Частина 1
Обмеження: 2 сек., 256 МіБ
Зустрілися якось працівники великих компаній і почали... Обговорювати план вулиці.
Виявляється, всі приміщення, які орендуватимуть ці компанії, збудують вздовж однієї вулиці.
\(i\)-та компанія орендуватиме офіс довжиною \(l_i\) метрів. Офіси будуватимуть один за одним, починаючи з точки 0. Всі працівники приїжджатимуть на стоянку, яку побудують в точці 0, та будуть йти до офісів своїх компаній.
Тобто, якщо офіси будуть збудовані в порядку \(p_1, p_2, ..., p_n\), то перший офіс почнеться в точці 0 і закінчиться в точці \(l_{p_1}\), другий почнеться в \(l_{p_1}\) і закінчиться в \(l_{p_1} + l_{p_2}\) і т.д. Двері кожного офісу завжди є в кінці будинку, який є ближчим до стоянки.
Ваше завдання — допомогти розмістити офіси компаній на цій вулиці в такому порядку, щоб сумарна відстань від точки 0 до усіх офісів була мінімальною.
Вхідні дані
У першому рядку задане ціле число \(n\) — кількість компаній.
У наступному рядку задано \(n\) цілих чисел \(l_i\) через пробіл — довжини офісів усіх компаній.
Вихідні дані
У єдиному рядку виведіть \(n\) чисел від 1 до \(n\) — порядок компаній, в якому варто будувати офіси.
Якщо існує декілька оптимальних порядків — виведіть будь-який із них.
Обмеження
\(1 \le n \le 10^5\),
\(1 \le l_i \le 10^4\).
Приклади
Вхідні дані (stdin) | Вихідні дані (stdout) |
---|---|
4 4 1 2 3 | 2 3 4 1 |
Примітки
Якщо розставити компанії у порядку 2, 3, 4, 1, то:
відстань до офісу першої компанії — 6,
відстань до офісу другої компанії — 0,
до офісу третьої компанії — 1,
до офісу четвертої компанії — 3,
сумарна відстань \(=6+0+1+3=10\).
Надіслати розв'язок
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|
Element Type | Створено | Хто | Задача | Компілятор | Результат | Час (сек.) | Пам'ять (МіБ) | № | Дії |
---|