|
|
|
|
|
|
|
Вернуться
| 1 Терентьев Михаил Павлович, 25 апреля 2023 г. 16:49:06 | |
|
Да, норм. На литкоде когда-то видел такую задачу
|
|
|
| 2 Меньшиков Фёдор Владимирович, 25 апреля 2023 г. 16:25:19 | |
|
Насчёт ответа для такого подотрезка. Там сложность в том, что X и Y там могут встречаться много раз. Можно идти слева направо и поддерживать, когда последний раз встретился X и когда Y. Если был X, был Y - то находим минимум от их позиций - и добавляем в ответ количество начал отрезка от самого начала до минимальной из этих двух позиций. Это будет количество допустимых отрезков для конца - текущей позиции. И этот же способ даёт возможность не выкидывать заранее числа меньше X и больше Y, нужно только иметь дополнительную переменную - где начался текущий отрезок допустимых чисел. Изначально это 0, как встречаем недопустимое число - переносим эту позицию на после него. И когда вычисляем количество начал - тоже от него. Итого O(n) по времени и O(1) по памяти.
|
|
|
| 3 Терентьев Михаил Павлович, 24 апреля 2023 г. 11:25:03 | |
|
Можете попробовать выкинуть из списка все числа, которые меньше X и больше Y. Тогда получится набор из подотрезков, в которых все числа в диапазоне [X;Y]. Далее посчитать ответ для каждого подотрезка и сложить результаты. Осталось научиться считать ответ для таких подотрезков
|
|
|
| 4 Тимур С, 24 апреля 2023 г. 11:17:00 | |
|
Пришла идея с двумя указателями, пока что думаю в эту сторону.
|
|
|
| 5 Тимур С, 24 апреля 2023 г. 11:16:13 | |
|
Например, дан массив [1, 5, 3, 1] X = 3, Y = 1. Ответ будет 1. Это всего лишь 1 подотрезок [3,1]. Я перебирал все подотрезки длины k(1 <= k <= n). Но возможно это сделать эффективнее?
|
|
|
| 6 Тимур С, 24 апреля 2023 г. 11:15:14 | |
Например, дан массив [1, 5, 3, 1] X = 3, Y = 1. Ответ будет 1. Это всего лишь 1 подотрезок [3,1].
Я перебирал все подотрезки длины k(1≤k≤n)k. Но возможно это сделать эффективнее?
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
