0 / 0 / 0
Регистрация: 20.02.2016
Сообщений: 18
|
|
1 | |
Что необходимо сделать20.02.2016, 00:43. Показов 9374. Ответов 34
Метки нет Все метки)
(
Диего увлекается коллекционированием наклеек. На каждой из них написано число, и каждый коллекционер мечтает собрать наклейки со всеми встречающимися числами.
Диего собрал N наклеек, некоторые из которых, возможно, совпадают. Как-то раз к нему пришли K коллекционеров. i-й из них собрал все наклейки с номерами не меньшими, чем pi. Напишите программу, которая поможет каждому из коллекционеров определить, сколько недостающих ему наклеек есть у Диего. Разумеется, гостей Диего не интересуют повторные экземпляры наклеек. Формат ввода В первой строке содержится единственное число N (0 ≤ N ≤ 100 000) — количество наклеек у Диего. В следующей строке содержатся N целых неотрицательных чисел (не обязательно различных) — номера наклеек Диего. Все номера наклеек не превосходят 109. В следующей строке содержится число K (0 ≤ K ≤ 100 000) — количество коллекционеров, пришедших к Диего. В следующей строке содержатся K целых чисел pi (0 ≤ pi ≤ 109), где pi — наименьший номер наклейки, не интересующий i-го коллекционера. Формат вывода Для каждого коллекционера в отдельной строке выведите количество различных чисел на наклейках, которые есть у Диего, но нет у этого коллекционера. Пример 1 Ввод 1 5 2 4 6 Вывод 0 1 Пример 2 Ввод 3 100 1 50 3 300 0 75 Вывод 3 0 2
0
|
20.02.2016, 00:43 | |
Ответы с готовыми решениями:
34
Что необходимо сделать, чтобы улучшить навыки программирования на PHP? HTML Forms. Что необходимо сделать для выполнения кода? Что необходимо сделать - когда полностью скопирован текст сайта? |
0 / 0 / 0
Регистрация: 20.02.2016
Сообщений: 18
|
|
20.02.2016, 01:59 [ТС] | 21 |
Ну в смсле у меня не видно какие тесты подаются на вход, только номера тестов видны и все
Добавлено через 7 минут Поможете, ребят?
0
|
![]() 1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
||||||
20.02.2016, 02:05 | 22 | |||||
Дже, Ошибки компиляции?
Добавлено через 2 минуты Дже, Попробуй так. Здесь без фишек с++11
0
|
![]() 495 / 377 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
|
|
20.02.2016, 02:07 | 23 |
а нам и не надо поиск проводить. он отсортирован уже, мы найдем ответ за сложность сета, и не надо каждый элемент проверять.
При этом сортировка в программе - уже плохо. И по-моему, если подсчитать сложность работы с сетом и сортировку вектора - то уже на этом только этапе алгоритм с сетом обгоняет сортировку вектора, не говоря уже что вектор еще необходимо заполнить, и найти в нем ответ на задачу. Покажите на фактах, и я поверю. Так то конечно вектор быстрей, но в том случае, если нам не нужны упорядоченные данные.
0
|
![]() 1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
20.02.2016, 02:12 | 24 |
_Valera_, По вашему set заполняется волшебным образом? При каждом добавлении элемента в set производится поиск, причем не по бинарному дереву, а по черно-красному, что хуже. Заполнение сета - не лучше, а хуже, чем сортировка вставками. сложность помните?
0
|
0 / 0 / 0
Регистрация: 20.02.2016
Сообщений: 18
|
|
20.02.2016, 02:29 [ТС] | 25 |
avgoor. wrong answer
Входные данные 1 5 2 4 6 Должно выйти 0 1 А выходит 1 0 Добавлено через 1 минуту Спасибо, Вам всем, что помогаете мне, но видимо мне суждено получить 2. Ведь срок сдачи завтра(
0
|
![]() 1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
20.02.2016, 02:31 | 26 |
У Диего 1 наклейка с номером 5.
К нему пришли двое. Одного не интересует 4 и меньше - ответ 1 Другого не интересует все что меньше 6. У Диего только 5 - ответ 0. Что я не так понял?
0
|
![]() 495 / 377 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
|
|
20.02.2016, 02:40 | 27 |
я помню. На цифрах покажешь? Хотел найти графики сравнения, но что то гугл на них не богат...
0
|
![]() 1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
||||||
20.02.2016, 02:42 | 28 | |||||
Тьфу, блин, позор на мои седые яйца. Перечитал условие внимательно. Должно быть так:
1
|
![]() 495 / 377 / 136
Регистрация: 27.01.2015
Сообщений: 1,588
|
|
20.02.2016, 02:42 | 29 |
Кстати, в твоем коде необходимость сортировки отпадает.
0
|
![]() 1379 / 406 / 144
Регистрация: 22.10.2014
Сообщений: 872
|
|
20.02.2016, 02:48 | 30 |
Красно-чёрное дерево это и есть бинарное дерево. С достаточно простой балансировкой. Так сказать золотая середина.
0
|
![]() 1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
||||||
20.02.2016, 02:59 | 31 | |||||
_Valera_, Nosey, Вот тест:
Еще вопросы есть? Добавлено через 1 минуту Вектор с сортировкой более чем в 10 раз быстрее! Добавлено через 4 минуты Тьфу, сорт забыл вставить. Всего лишь в 2 раза быстрее.
0
|
20.02.2016, 03:17 | 32 |
0
|
20.02.2016, 03:19 | 33 |
Не по теме: Nosey, про вопросы это не вам, а про бинарное дерево - имелось ввиду обычное сбаллансированное бинарное дерево, без дополнительных атрибутов вершин.
0
|
20.02.2016, 03:24 | 34 |
0
|
20.02.2016, 03:33 | 35 |
Не по теме: Nosey, Ну у RB в 50% случаев - адский труд. Просто оно нужно только тогда, когда в перемешку идут вставки и удаления. Там можно получить выигрыш. А вот там, где только вставки - вектор рулит.
0
|
20.02.2016, 03:33 | ||||||
Помогаю со студенческими работами здесь
35
Через что лучше сделать плеер, необходимо открытие только avi файлов?
Что необходимо сделать, чтобы программа, написанная в Embarcadero RAD Studio Berlin 10.1 запустилась на другом Что необходимо сделать, если нужно перенести источник ЭДС из какой-либо ветви электрической цепи в другую? Необходимо сделать вставку <b></b> по краям выделенного текста в Memo1, к примеру, что бы получился такой результат: <b>01</b>. Кто сможет помочь? Искать еще темы с ответами Или воспользуйтесь поиском по форуму:
|
|
Новые блоги и статьи
![]() |
||||
Простая нейросеть на КуМир: Создание и обучение
EggHead 16.03.2025
Искусственные нейронные сети — удивительная технология, позволяющая компьютерам имитировать работу человеческого мозга. Если вы хотя бы немного интересуетесь современными технологиями, то наверняка. . .
|
Исполнитель Кузнечик в КуМир: Решение задач
EggHead 16.03.2025
Среди множества исполнителей в системе КуМир особое место занимает Кузнечик — простой, но невероятно полезный виртуальный персонаж, который перемещается по числовой прямой, выполняя ваши команды. На. . .
|
Исполнитель Водолей в КуМир: Решение задач
EggHead 16.03.2025
Разработка алгоритмического мышления — одна из ключевых задач для начинающих программистов, и система КуМир предлагает отличный способ погрузиться в этот процесс. Среди множества исполнителей в этой. . .
|
Исполнитель Чертежник в КуМир: Решение задач
EggHead 16.03.2025
Представьте, что вы можете рисовать на бесконечной координатной плоскости, перемещая точку, которая оставляет след. По вашей команде она может поднять перо и двигаться, не оставляя следа, или. . .
|
Исполнитель Робот в КуМир: Решение задач
EggHead 16.03.2025
КуМир (Комплект Учебных МИРов) — это учебная среда программирования, разработанная специально для обучения базовым концепциям алгоритмизации. Её главная фишка — использование русскоязычного. . .
|
Исполнитель Черепаха в КуМир: Решение задач
EggHead 16.03.2025
Представьте, что вы впервые учитесь программировать, а перед вами стоит задача заставить маленькую виртуальную черепашку рисовать на экране. Звучит забавно? Эта идея зародилась ещё в 1967 году, когда. . .
|
Конвейеры данных с Apache Kafka
Javaican 16.03.2025
В мире, где данные стали новой нефтью, Apache Kafka зарекомендовал себя как мощный инструмент для построения надежных и масштабируемых конвейеров данных. Созданный изначально командой LinkedIn в 2011. . .
|
Deno против Node.js: Будущее JavaScript рантайма
run.dev 16.03.2025
За последнее десятилетие Node. js стал абсолютным лидером среди JavaScript-рантаймов и фактическим стандартом для серверной разработки на JavaScript. Но в 2018 году тот же разработчик, который создал. . .
|
SwiftUI или UIKit - что выбрать для нового приложения iOS?
mobDevWorks 16.03.2025
Когда Apple представила SwiftUI на WWDC 2019, многим показалось, что дни UIKit сочтены. Новый декларативный фреймворк предлагал радикально иной подход к разработке интерфейсов. Вместо кропотливого. . .
|
Docker: Руководство для начинающих по созданию первого приложения
Mr. Docker 16.03.2025
Docker — это платформа, которая упаковывает ваше приложение и все его зависимости в стандартизированные блоки, называемые контейнерами. Эти контейнеры изолированы друг от друга и от основной системы,. . .
|