@Sheephard

Как разбить список на подсписки?

Дана задача:
Необходимо разбить список на минимальное количество подсписков так, чтобы в каждом из подсписков первый элемент был минимальным в нём, а последний -- максимальным.

Первая строка входных данных содержит целое число n (1 ≤n≤ 300000) — количество элементов в заданной последовательности.

Вторая строка содержит n целых чисел a1,a2, ...,an — заданную последовательность (1 ≤ai≤ 109).
Выходные данные

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

Примеры:
Ввод:
6
2 3 1 1 5 1
Вывод:
3

Ввод:
4
1 3 2 4
Вывод:
1

Ввод:
5
5 4 3 2 1
Вывод:
5


Мой код:
flen = int(input())
l = [int(i) for i in input().split()]

vmin = l[0]
imax = 0
k = 1
i = 1
# барьер
l.append(0)

while i <= flen-1:
    if l[i] > l[imax]:
        imax = i
    elif l[i] < vmin or (l[i] == vmin and l[imax] > vmin):  # начало нового подсписка 
        vmin = l[imax+1]
        i = imax + 1
        imax += 1
        k += 1
        continue
    i += 1

print(k)


Тестирующая программа выдаёт неверный ответ, хотя на моих тестовых данных всё хорошо.
В чём может быть ошибка?
  • Вопрос задан
  • 77 просмотров
Решения вопроса 1
hint000
@hint000
у админа три руки
Будет достаточно, если я приведу тест, на котором ваша программа ошибается?
вот такой тест:
4
1 2 1 3
правильный ответ: 1
ответ вашей программы: 2
P.S. ладно, ошибка в этой части: or (l[i] == vmin and l[imax] > vmin)
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы