Тут нужно найти отрезок с максимальным количеством человек. Я сначала думал перебирать места. Но проблема в том что для каждого человека n различных отрезков. итого O(n^2).
1 лайк
Подумай выгодно ли размещать людей на отрезок l...r где на l-ом месте и на r-ом месте нету людей?
Дальше пруф :
Спойлер
Пусть мы хотим расположить людей в такой отрезок, пусть кол-во людей которое нужно переместить будет cost(l, r) (cost(l, r) = n - cnt(l, r), где cnt(l, r) это количество людей на отрезке l, r). Тогда можно заметить что для таких отрезков всегда будет выполняться cost(l, r) \geq cost(l + 1, r) и cost(l, r) \geq cost(l, r - 1). Почему это так сам докажи, там легко.
Ну и очевидно что таких отрезков длины n всего будет 2 * n.
5 лайков
(не читал пруф) не выгодно. Ну можно собирать отрезки на которых на l и r стоят люди и len <= n. Если продлевать отрезки ничего не измениться.
1 лайк
Мысль была в том что нужны только отрезки длины n у которых на одному из краёв хотя бы один чел стоит, и попробуй посчитать сколько таких отрезков будет
1 лайк
Как я понял от того что мы собираем отрезки где с концов сидят люди у нас ответ не поменяется. Я думаю что можно перебирать левого человека и бпшкой находить правого человека указывая что нам нужен отрезок максимум длины n. Потом преф суммой находить то что между ними. И таких отрезков не будет много ~n
Так по задаче нам нужен отрезок ровно длины n
2 лайка
да но можно же просто продлить. Идея в том что с концов точно будут два крайних сидячих человека
Я хз зачем тебе второй человек , перечитай цитату ниже и попробуй сделать что я сказал.
3 лайка
Понял. Но ведь максимум n таких отрезков будет же. Так как n человек есть у нас
2 * n вроде, для человека x может быть два отрезка (x - n + 1, x) и (x, x + n - 1).
Ну и всё теперь таких отрезков не n^2, а значит ты можешь делать то что хотел
2 лайка
Но ведь нам не обязательно рассматривать случай когда x у нас правая граница? Да?
хз, главное то что отрезков линейное количество
1 лайк