Уведомления

Группа в Telegram: @pythonsu

#1 Фев. 8, 2024 02:20:13

Andrew13
Зарегистрирован: 2024-02-08
Сообщения: 2
Репутация: +  0  -
Профиль   Отправить e-mail  

Решение задачки с контеста

Всем привет !

Прошу помочь с решением задачки с яндекс контеста
Перечитал условие раз 5 и так и не понял с чего начать(

Марсоход раз в час записывает в массив информацию о солнечной радиации. Каждое значение — это число от 0 до 100.

Для каждого элемента требуется определить, сколько в массиве есть значений меньше, чем текущее. Результат нужно записать во второй массив.

Исходные массивы могут быть длиной от 2 до 500 элементов.

Например, исходный массив — nums = .

Берём первое значение массива, это 8. Сравниваем это число с остальными: считаем, сколько в массиве есть чисел, меньших, чем выбранное. В этом массиве четыре числа, меньших, чем 8. Создаём массив result, записываем в него 4.

Точно так же проверяем второе значение в исходном массиве, это единица. В исходном массиве нет ни одного числа, меньшего, чем 1. В массив result записываем второе значение: 0.

Проверяем третье значение в массиве nums, это 2. Есть только одно значение, меньшее, чем 2. В массив result записываем третье значение — 1.

Таким же образом проверяем все остальные значения в nums.

В итоге для входного массива получится результирующий массив .

Решить задачу можно любым образом, пусть даже не самым эффективным. Решение за квадратичное время вполне подойдёт.

Если останутся время и силы, попробуйте найти решение с временной сложностью О(n log n), такое тоже есть.

Формат ввода
Массив целых чисел, записанных через пробел, — показатели радиации.

Формат вывода
Массив целых чисел, записанных через пробел, где каждое число — это количество чисел в исходном массиве, меньших, чем рассматриваемое.


Пример ввода и вывода на скрине

Отредактировано Andrew13 (Фев. 8, 2024 02:21:26)

Офлайн

#2 Фев. 8, 2024 02:21:45

Andrew13
Зарегистрирован: 2024-02-08
Сообщения: 2
Репутация: +  0  -
Профиль   Отправить e-mail  

Решение задачки с контеста

+++

Прикреплённый файлы:
attachment 36.GIF (8,9 KБ)

Офлайн

#3 Фев. 8, 2024 02:29:34

py.user.next
От:
Зарегистрирован: 2010-04-29
Сообщения: 9873
Репутация: +  853  -
Профиль   Отправить e-mail  

Решение задачки с контеста

Тут секрет, знаешь, в чём? Если ты хотя бы раз прошёлся по массиву и посчитал эти элементы, то ты за этот проход мог построить структуру всех остальных пройденных элементов в массиве, запомнив их не хаотично, как они лежали изначально, а в каком-то отсортированном виде. Поэтому при втором прохождении ты можешь их искать уже не в хаотичном массиве, а в отсортированной структуре своей. Так ты можешь быстрее получать количество этих искомых элементов.



Отредактировано py.user.next (Фев. 8, 2024 02:29:57)

Офлайн

#4 Фев. 23, 2024 19:36:57

Rogal
Зарегистрирован: 2024-02-20
Сообщения: 11
Репутация: +  0  -
Профиль   Отправить e-mail  

Решение задачки с контеста

Действительно, звучит логично

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version