1. Главная
  2. Библиотека
  3. Программирование
  4. Андрей — отличный стрелок. Он никогда не промахивается. Сегодня на тренировке он хочет поразить максимальное количество м...

Андрей — отличный стрелок. Он никогда не промахивается. Сегодня на тренировке он хочет поразить максимальное количество мишеней. Мишени появляются внезапно, иногда даже одновременно, но всегда в моменты времени, выраженные целыми положительными

«Андрей — отличный стрелок. Он никогда не промахивается. Сегодня на тренировке он хочет поразить максимальное количество мишеней. Мишени появляются внезапно, иногда даже одновременно, но всегда в моменты времени, выраженные целыми положительными»
  • Программирование

Условие:

Напиши код на питоне для решения данной задачи:
Андрей — отличный стрелок. Он никогда не промахивается. Ему очень нравится стрелять по внезапно появляющимся мишеням.

Сегодня на тренировке он хочет поразить максимальное количество мишеней. Мишени появляются внезапно, иногда даже одновременно, но всегда в моменты времени, выраженные целыми положительными числами.

Каждая мишень может «убита» в течение лишь одной секунды с момента её появления. Будем считать, что выстрел происходит мгновенно, поэтому поразить мишень можно в любой момент этой одной секунды: в самом её начале, в конце или в любой другой промежуточный момент между.

На перезарядку ружья у Андрея уходит ровно 1
секунда, а одной перезарядки хватает только на один выстрел. В начальный момент времени (момент времени, равный 0
) ружьё у Андрея заряжено. Кроме того, Андрей успевает зарядить ружьё и выстрелить по мишени, если мишень появилась в тот же момент, в который он начал перезаряжать ружьё.

По известным моментам времени появления мишеней посчитайте максимальное количество мишеней, которые может поразить Андрей.

Входные данные
В первой строке вводится натуральное число N
— количество мишеней (1≤N≤2⋅105)
.

Во второй строке записано N
целых чисел — моменты появления мишеней ti
, выраженные в секундах от начала тренировки. Каждый момент появления мишени ti
— это целое число из промежутка [1;109]
.

Выходные данные
Выведите одно целое число — максимальное количество мишеней, которые может поразить Андрей.

Решение:

Для решения этой задачи мы можем использовать жадный алгоритм. Основная идея заключается в том, чтобы отслеживать время, когда Андрей может стрелять по мишеням, и выбирать мишени, которые появляются в тот момент, когда он может их поразить. Вот шаги, которые мы будем выполнять: 1. Сначала отсортируем моменты появления мишеней. Это позволит нам обрабатывать их в порядке времени. 2. Инициализируем переменную для отслеживания времени, когда Андрей сможет снова стрелять. 3. Проходим по каждому моменту появления мишени: - Если момент появления мишени больше или равен времени, когда Андрей смож...

Не нашел нужную задачу?

Воспользуйся поиском

Выбери предмет