Сбор вишни

@Фнтон200 · Регистрация: 21.07.2019

Author24 — интернет-сервис помощи студентам

Задача не проходит по Time Limit. Всё перепробовал, не знаю, как оптимизировать.

Задача:
У Макса в огороде есть большой вишневый сад, состоящий из N деревьев, расположенных по кругу. На каждом из деревьев висит некоторое количество вишен.
Макс хочет собрать ягоды, а для этого выбрать дерево с которого начинать сбор и идти по кругу, либо по часовой, либо против часовой стрелки. Макс решил собирать ягоды в ведра, каждое из которых вмещает K вишен. Сбор ягод с высоких деревьев – трудоемкая задача, поэтому для удобства Макс хочет, чтобы вместимости текущего ведра всегда хватало, чтобы собрать всю вишню с дерева полностью. Тогда, если вместимости ведра не хватает, Макс кладет текущее ведро и берет новое.

Макс хочет выбрать точку начала и направление оптимально так, чтобы использовать как можно меньшее количество ведер.

Выведите минимальное количество ведер, которое понадобится Максу для сбора всех ягод.

Входные данные:
Первая строка содержит целые числа N и K — соответственно количество деревьев и вместимость одного ведра.

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

Выходные данные
Выведите одно целое число — количество ведер, которое понадобится Максу, чтобы собрать всю вишню.

Примеры:
входные данные
5 10
3 3 3 7 2
выходные данные
2
входные данные
7 10
3 3 7 3 4 4 3
выходные данные
3

Мой код (не проходит по Time Limit):

Python

n, m = map(int, input().split())
l = [int(i) for i in input().split()]
mimi = (sum(l) - 1) // m + 1
ans = n
 
for i in range(0, n, 2):
    kol = 1
    now = 0
    for j in range(n):
        if now + l[j] > m:
            kol += 1
            now = l[j]
        else:
            now += l[j]
    ans = min(ans, kol)
    if ans == mimi:
        break
    l = l[2:] + [l[0], l[1]]
 
print(ans)

@hacthies · 29.09.2019, 15:37

Фнтон200, скинь ограничения по времени и n какой может быть

@Фнтон200 · 29.09.2019, 15:46 **[ТС]**

ограничение по времени на тест 2 секунды
ограничение по памяти на тест 64 мегабайта
1 <= n <= 2 * 10 в 5

@hacthies · 30.09.2019, 17:11

Фнтон200, когда решаешь задачу, прикидывай время работы по твоему решению. У тебя нелегкое решение. 1) И так ~1/2n², но это еще не страшно, 2) Срезы работают за один проход массива, т. е. то же самое, что for (n).

Сообщение от Фнтон200

for i in range(0, n, 2):

Сообщение от Фнтон200

for j in range(n):

Сообщение от Фнтон200

l = l[2:] + [l[0], l[1]]

Ну, если n - 200000, вроде бы не очень страшно, но, с учетом split`а (он вроде бы не очень быстрый) и остального, может и не пройти.
Сейчас подумаю, как оптимизировать (я особо то и условий не читал)

@hacthies 8 / 12 / 2 Регистрация: 08.08.2019 Сообщений: 63
	29.09.2019, 15:37	2
	Фнтон200, скинь ограничения по времени и n какой может быть 0

@Фнтон200 0 / 0 / 0 Регистрация: 21.07.2019 Сообщений: 3
	29.09.2019, 15:46 [ТС]	3
	ограничение по времени на тест 2 секунды ограничение по памяти на тест 64 мегабайта 1 <= n <= 2 * 10 в 5 0

@hacthies 8 / 12 / 2 Регистрация: 08.08.2019 Сообщений: 63
	30.09.2019, 17:11	4
	Фнтон200, когда решаешь задачу, прикидывай время работы по твоему решению. У тебя нелегкое решение. 1) И так ~1/2n², но это еще не страшно, 2) Срезы работают за один проход массива, т. е. то же самое, что for (n). Сообщение от Фнтон200 for i in range(0, n, 2): Сообщение от Фнтон200 for j in range(n): Сообщение от Фнтон200 l = l[2:] + [l[0], l[1]] Ну, если n - 200000, вроде бы не очень страшно, но, с учетом split`а (он вроде бы не очень быстрый) и остального, может и не пройти. Сейчас подумаю, как оптимизировать (я особо то и условий не читал) 0