@asdsdsdafsdafdsaf

Как найти сумму чисел на нечетных позициях после сортировки массива?

Дан массив из N чисел, как найти сумму тех чисел, которые будут стоять на нечетных местах после сортировки массива?
Понятно, что можно отсортировать массив и пройтись по нему ещё раз, но как сделать быстрее?
Сама задача:
61a49d6fe6d7d414914034.png
  • Вопрос задан
  • 149 просмотров
Пригласить эксперта
Ответы на вопрос 2
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Никак. Есть методы получить число, которое будет стоять на заданной позиции (или числа на отрезке) в отсортированном массиве быстрее сортировки (алгоритм QuickSelect). Как-то быстрее сортировки найти все числа на нечетных позициях - нельзя.

Edit: Если стандартная сортировка не работает и L большое, то стоит посмотреть в сторону radix sort. Если бы L было относительно небольшим - то лучший вариант был бы сортировка подсчетом.
Ответ написан
Alexandroppolus
@Alexandroppolus
кодир
Есть подозрения, что задача не на пустом месте появилась.
По сути, у нас тут только 4 входных параметра.
Теоретически эта сумма должна вычисляться за О(1).
Попробуй повычислять на разных наборах параметров, найти какие-то закономерности в результатах...
Ответ написан
Ваш ответ на вопрос

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

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