ПОМОГИТЕ ИНФОРМАТИКА PYTHON !!!. Агрокомплекс «Дикое поле»
14.03.2022
Дата публикации:

ПОМОГИТЕ ИНФОРМАТИКА PYTHON !!!. Агрокомплекс «Дикое поле»

9380d1a7

ПОМОГИТЕ ИНФОРМАТИКА PYTHON !!!. Агрокомплекс «Дикое поле» представляет собой n полей, вытянувшихся в ряд. Поля пронумерованы, начиная с единицы. Комплекс находится в слабозаселённой зоне, и поэтому наблюдение за полями осуществляется с помощью дронов «Пеларгония». Агрокомплекс располагает двумя такими дронами. Один начинает облёт с первого поля, второй – с поля номер n; оба дрона движутся навстречу друг другу, последовательно осматривая поля. Они отличаются по размерам, поэтому на осмотр каждого поля требуется разное время. При этом перелёт с одного поля на другое занимает фиксированное время. Определите, за какое минимальное время дроны осмотрят все поля. Если одна «Пеларгония» уже осматривает поле, вторая на него не влетает. Формат ввода На вход программе в первой строке подаётся натуральное число N (3 ≤ N ≤ 1000000) – количество полей. Во второй строке подаётся натуральное число T ( T≤ 1000 минут) – время перелёта между соседними полями. Далее в N строках подаётся по одному натуральному числу ti (ti ≤ 1000 минут) – время осмотра поля номер i. Формат вывода Вывести одно натуральное число – минимально возможное время осмотра всех полей агрокомплекса.

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

Сначала отсортируем время осмотра полей в порядке возрастания. Затем создадим два указателя - один будет указывать на первое поле, а второй на последнее поле.

Заведем переменную total_time и инициализируем ее нулем.

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

Когда указатели встретятся (то есть первый указатель станет больше или равен второму), мы получим минимальное время осмотра всех полей.

Выведем значение total_time.

Пример реализации на языке Python:

n = int(input())
T = int(input())

fields = []
for _ in range(n):
    fields.append(int(input()))

fields.sort()

left = 0
right = n - 1
total_time = 0

while left < right:
    total_time += fields[left] + fields[right] + T
    left += 1
    right -= 1

if left == right:
    total_time += fields[left]

print(total_time)

Пример работы программы:

Входные данные:

5
2
3
4
1
5
2

Выходные данные:

19

В данном примере первый дрон осматривает поля в порядке 1, 2, 3, второй дрон - в порядке 5, 4. Общее время осмотра всех полей равно 19 минут.