Условие:
ограничение по времени на тест: 3 s .
ограничение по памяти на тест: 1024 MB
В вашем плейлисте на сайте MeValve сейчас содержится n очень интересных и познавательных видео. i-е видео длится ровно di минут.
MeValve в своей обычной манере увеличил частоту и продолжительность показа рекламы. Во вселенной добра и справедливости, где вы находитесь, реклама на MeValve показывается только МЕЖДУ видео. После видео реклама показывается тогда и только тогда, когда соблюдается любое из условий ниже:
- с показа последней рекламы было просмотрено 3 видео;
- с показа последней рекламы прошло хотя бы k минут.
Для выполнения домашней работы вам срочно нужно посмотреть все n видео в вашем плейлисте. Зная, что вы только что просмотрели рекламный ролик, выберите такой порядок просмотра видео, чтобы минимизировать количество просмотренных рекламных вставок. Следующее видео начинается сразу после того, как заканчивается предыдущее видео либо реклама, и после последнего ролика рекламу смотреть не обязательно (шах и мат, Googleплекс) |
Входные данные
В первой строке записано единственное целое число t(1 ≤ t ≤ 100000) - Количество наборов входных данных.
Первая строка каждого набора состоит из пары натуральных чисел n и k(1 ≤ n ≤ 100000,1 ≤ k ≤ 30000) - количество видео и временной интервал между показами рекламы соответственно.
В следующей строке даны n чисел d{1}, d{2}, \ldots, d{n}≤ft(1 ≤ d{i} ≤ 10000\right) - продолжительности роликов в плейлисте.
Сумма n по всем тестам не превосходит 106.
Выходные данные
В ответ на каждый тестовый набор выведите минимальное количество рекламных роликов, которое необходимо посмотреть.
Пример
\begin{tabular}{|l|l|}
\hline входные данные & Скопировать \\
\hline μlticolumn{2}{|l|}{5} \\
\hline 825 & \\
\hline μlticolumn{2}{|l|}{\begin{array}{llllllll}4 & 5 & 18 & 3 & 17 & 17 & 18 & 14\end{array}} \\
\hline μlticolumn{2}{
Решение:
Для решения данной задачи, нам нужно минимизировать количество рекламных вставок при просмотре видео. Мы будем использовать жадный подход, чтобы определить порядок просмотра видео, который позволит нам избежать показа рекламы как можно чаще.
Шаг 1: Понимание условий показа рекламы
Реклама показывается:1. Если просмотрено 3 видео подряд.
2. Если с момента последнего показа рекламы прошло хотя бы k минут.
Шаг 2: Подход к решению
1. Сортировка видео: Для минимизации времени между рекламными вставками, мы можем отсортировать видео по их длительности в порядке убывания. Это позволит нам сначала смотреть самые длинные видео, что увеличит общее время просмотра и уменьшит вероятность показа рекламы.2. Итерация по видео: Мы будем просматривать видео одно за другим, отслеживая общее время просмотра и количество просмотренных видео. После каждого видео мы будем проверять, нужно ли показывать рекламу.
3. Условия для рекламы:
- Если просмотрено 3 видео, показываем рекламу.
- Если общее время просмотра с последнего показа рекламы превышает k минут, показываем рекламу.
Шаг 3: Реализация алгоритма
Теперь мы можем реализовать алгоритм на Python:- Мы принимаем количество тестов и список тестовых случаев. - Для каждого теста: - Сортируем длительности видео. - Инициализируем счетчик рекламы и переменные для отслеживания времени и количества просмотренных видео. - Проходим по каждому видео, обновляя общее время и количество просмотренных видео. - Проверяем условия для показа рекламы и обновляем счетчик. - В конце выводим результаты для каждого теста. Этот алгоритм эффективно минимизирует количество рекламных вставок, соблюдая условия задачи. Он работает за O(n log n) из-за сортировки и O(n) для итерации по видео, что в сумме дает O(n log n) для каждого теста.