Помогите с заданием

Question

Очередь задач 
 
Есть план выполнения задач некоторой известной продолжительности. В этом плане имеется информация о том сколько задач выполняется в каждый момент времени. Моменты времени равнозначны и для простоты описания можем считать что один момент времени - это одна секунда. 
 
Надо найти в этой очереди интервал заданного размера, в который очередь наименее загружена. 
 
Формат ввода 
В первой строке вводится натуральное число  
𝑁 N ( 1 ≤ 𝑁 ≤ 1 0 5 1≤N≤10  5  ) - количество моментов времени, и натуральное число  
𝑇 T ( 1 ≤ 𝑇 ≤ 𝑁 1≤T≤N) - размер искомого временного интервала.
В следующих  𝑁 
N строках подаются числа  𝑎 𝑖 a  i ( 1 ≤ 𝑎 𝑖 ≤ 1 0 5 1≤a  i  ≤10  5  ) - число задач в секунду  𝑖 i. 
 
Формат вывода 
Выведите номер секунды, в которую начинается искомый интервал - интервал размера  𝑇 
T, в который очередь была наименее загружена. Если есть несколько подходящих ответов - выведите наименьший.

Пример 
Ввод                Вывод 
  7 3                           5
3
5 
2 
8 
4 
3 
2

Примечание 
С первой по третью секунды:  
3 + 5 + 2 = 10 
3+5+2=10, со второй по четвертую:  
5 + 2 + 8 = 15 
5+2+8=15, с третьей по пятую:  
2 + 8 + 4 = 14 
2+8+4=14, с четвертой по шестую:  
8 + 4 + 3 = 15 
8+4+3=15, с пятой по седьмую:  
4 + 3 + 2 = 9 
4+3+2=9

Ограничение памяти 256.0 Мб 
 Ограничение времени 1 с 
 Ввод 
 стандартный ввод или input.txt 
 Вывод 
 стандартный вывод или output.txt

Валентин Артамонов · Answer

Для решения этой задачи можно использовать алгоритм скользящего окна (sliding window). Этот алгоритм позволяет эффективно находить минимальную сумму в подмассиве заданной длины. 
 
Алгоритм: 
Инициализация: Считываем входные данные и создаем массив, хранящий количество задач в каждую секунду. 
 
Суммирование первого интервала: Вычисляем сумму первых T секунд. 
 
Скользящее окно: Двигаем окно по массиву, вычитая значение, которое выходит за пределы окна, и добавляя новое значение, которое входит в окно. 
 
Поиск минимума: В процессе движения окна отслеживаем минимальную сумму и соответствующий ей индекс начала интервала. 
 
Вывод результата: Выводим индекс начала интервала с минимальной суммой. 
 
Пример кода: 
python

def find_least_loaded_interval(N, T, tasks): 
    # Вычисляем сумму первых T секунд 
    current_sum = sum(tasks[:T]) 
    min_sum = current_sum 
    min_index = 0 
 
    # Проходим по массиву с помощью скользящего окна 
    for i in range(1, N - T + 1): 
        # Обновляем текущую сумму, вычитая значение, которое выходит за пределы окна, 
        # и добавляя новое значение, которое входит в окно 
        current_sum = current_sum - tasks[i - 1] + tasks[i + T - 1] 
         
        # Если текущая сумма меньше минимальной, обновляем минимальную сумму и индекс 
        if current_sum < min_sum: 
            min_sum = current_sum 
            min_index = i 
 
    return min_index + 1  # Возвращаем индекс, начиная с 1 
 
# Чтение входных данных 
import sys 
input =  sys.stdin.read  
data = input().split() 
 
N = int(data[0]) 
T = int(data[1]) 
tasks = list(map(int, data[2:])) 
 
# Находим и выводим результат 
result = find_least_loaded_interval(N, T, tasks) 
print(result) 
Как это работает: 
Инициализация: Считываем количество секунд N и размер интервала T. Затем считываем массив задач. 
 
Первый интервал: Вычисляем сумму первых T элементов. 
 
Скользящее окно: Двигаем окно по массиву, обновляя сумму и отслеживая минимальную сумму и соответствующий индекс. 
 
Вывод результата: Выводим индекс начала интервала с минимальной суммой. 
 
Пример работы: 
Для входных данных:

7 3 
3 
5 
2 
8 
4 
3 
2 
Программа выведет:

5 
Этот алгоритм работает за линейное время O(N), что достаточно эффективно для заданных ограничений.