|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
04.03.2022, 01:14 | #1 |
Регистрация: 07.02.2022
Сообщений: 4
|
C#, гонки на подах, ускорить выполнение кода
Мой код проходит первые тесты, но потом на вход идет 100000+ чисел и время превышает максимальное в 1 сек, как можно его ускорить?
Задание: Гонки на подах популярный вид развлечений. Удовольствие от них способны получить и участники, и зрители, и букмекерские конторы, принимающие ставки на результат очередной гонки. При этом владельцы букмекерских контор периодически совершают некоторые незаконные действия, чтобы повлиять на итоговые позиции гонщиков. Например, можно испортить тормозную систему в некоторых подах, после чего гонщику придется ехать существенно медленнее обычной скорости ради сохранения контроля гонщика над машиной. Выяснилось, что в последней гонке участвовали n гонщиков. У каждого из гонщиков на машине был написан номер — число от 1 до n, номера всех гонщиков различались. Также известно, что владельцы одной из букмекерских контор испортили тормозную систему во всех машинах, номера которых превосходили некоторое число k. Любая машина с испорченной тормозной системой будет ехать медленнее, чем любая машина с исправными тормозами. Соответственно, в протоколе с результатами гонки у любой машины с номером большим, чем k, место будет также больше, чем k. Вы проводите расследование этого неприятного инцидента. В качестве первого шага расследования вы решили найти все возможные значения числа k, изучая только результаты гонки. Формат ввода: В первой строке входного файла содержится одно целое число n (1 ≤ n ≤ 100 000) — количество гонщиков, участвовавших в соревновании. Вторая строка содержит n различных чисел ai (1 ≤ ai ≤ n) — протокол с результатами гонки, где ai — номер машины, которая заняла i-ое место. Формат вывода: В первой строке выходного файла выведите одно целое число c — количество возможных значений числа k. В следующей строке выведите c натуральных чисел, разделенных пробелами — возможные значения числа k. Все числа во второй строке должны быть различны и не должны превосходить n. Числа во второй строке должны быть упорядочены по возрастанию. Код:
|
04.03.2022, 16:32 | #2 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,342
|
У вас сложность получилась O(N^2), если не путаю. Чтобы ускорить нахождение ответа, нужно упростить алгоритм. Особо не тестировал:
Код:
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
05.03.2022, 18:00 | #3 |
Регистрация: 07.02.2022
Сообщений: 4
|
BDA, Спасибо, помогло
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Гонки на подах | POrro | Фриланс | 3 | 01.03.2022 18:43 |
Sleep останавливает выполнение всего в программе а не задерживает выполнение конкретного куска кода? | Illusiony | Общие вопросы Delphi | 19 | 22.02.2015 18:37 |
Ускорить выполнение цикла | elen_7C9 | Общие вопросы C/C++ | 5 | 21.10.2012 22:06 |
Можно ли ускорить выполнение этого кода? | Velross | Помощь студентам | 3 | 07.01.2010 19:37 |
Можно ли как-то ускорить выполнение этого кода (обработка примечаний)? | motorway | Microsoft Office Excel | 2 | 23.07.2009 17:06 |