1 / 1 / 0
Регистрация: 11.12.2021
Сообщений: 18
|
|
1 | |
Нахождение самого длинного подмассива одинаковых чисел с возможностью удаления до k чисел29.08.2023, 17:43. Показов 1576. Ответов 9
Нужно найти самый длинный подмассив массива состоящий из одинаковых чисел, притом можно удалить до k чисел.
Формат входных данных В первой строке входа заданы два целых числа n и k (1 ≤ n ≤ 1 000 000, 1 ≤ k ≤ 1 000 000) — длина массива и количествоо чисел которые можно удалить. В следующей строке заданы n целых чисел c_i (1 ≤ c_i ≤ n) — элементы массива Формат результата Выведите одно число — максимальную длину последовательности, которую можно получить, удаляя числа Примеры Входные данные 8 2 2 4 4 2 1 4 2 4 Результат работы 3
0
|
29.08.2023, 17:43 | |
Ответы с готовыми решениями:
9
Замена самого короткого и самого длинного чисел местами определить в массиве длину самого длинного ряда повторяющихся чисел Вывести индексы начала и конца самого длинного участка, состоящего только из положительных чисел Нахождение самого длинного слова Нахождение самого длинного слова |
3697 / 2647 / 761
Регистрация: 29.06.2020
Сообщений: 9,800
|
|
29.08.2023, 21:16 | 3 |
Извини, какая формула при задаче на перебор/подсчет ?
Нужно считать одинаковые числа и количество чисел между ними. Потом выбрать наибольшую по допустимым k. Добавлено через 5 минут Если я не ошибаюсь, это довольно распространенная задача тут. ТС мог бы воспользоваться поиском.
0
|
3697 / 2647 / 761
Регистрация: 29.06.2020
Сообщений: 9,800
|
|
29.08.2023, 22:12 | 5 |
Поделишься ? )
Добавлено через 2 минуты Хотя если брутфорсить, то не нужно.
0
|
3697 / 2647 / 761
Регистрация: 29.06.2020
Сообщений: 9,800
|
||||||
29.08.2023, 23:05 | 7 | |||||
КодВыделить код
n = 10 k = [0,1,2,3] 1 2 4 4 2 1 4 1 4 4 const U = 3 k = 0 x = 10-3 > 0 ? 10 - 0 : 10 - 3; Можно я дальше не буде ? Добавлено через 2 минуты Самым брутальным брутфорсом. Конечно при таких входных, я думаю он загнется. Но всё же. Для завтра есть идейка )
Байт, тут формулой не получится, потому что расположение чисел играет огромную роль.
0
|
1 / 1 / 0
Регистрация: 12.02.2016
Сообщений: 15
|
|
30.08.2023, 02:14 | 9 |
Для каждого уникального числа (цвета) в массиве массив можно представить как череду интервалов (полос) этого цвета (одноцветных) и полос из элементов других цветов (разноцветных). В итоге нужно определиться, с какой одноцветной полосы будет эффективнее всего начинать подмассив, учитывая то, что мы будем идти справа налево и удалять разноцветные полосы, сколько для этого хватит K, для того, чтобы склеились одноцветные и длина подмассива (склеенной полосы) была максимальной. И максимум (по цветам) максимальной длины склеенной полосы и будет ответом.
Т.к. 1 ≤ n ≤ 1 000 000 и 1 ≤ c_i ≤ n, то допустимо использовать О(n) памяти и допустимо иметь массив, в котором можно будет обращаться к данным по индексами цветов. Ну и идём по исходному массиву, как только встретим новый цвет, выдвигаем его начало в кандидаты на начало склеенной полосы. Когда c_i == c_i-1 обновляем конец текущей склеенной полосы этого цвета, когда c_i != c_i-1 смотрим, хватает у нас остатков K или нет, чтобы приклеить начало новой полосы цвета c_i. Если нет, то кандидатура начала склеенной полосы переходит на следующую полосу, обновляется текущий максимум длины склеенной полосы, отменяем удаление разноцветной полосы, которая идёт перед новой кандидатурой и пр.
0
|
30.08.2023, 02:25 | 10 |
ощущение что двумерная динамика
0
|
30.08.2023, 02:25 | |
30.08.2023, 02:25 | ||||||
Помогаю со студенческими работами здесь
10
Нахождение самого длинного слова в строке LISP, нахождение самого длинного слова Нахождение самого длинного палиндрома в строке Нахождение самого длинного слова в строке Нахождение самого длинного слова в строке Искать еще темы с ответами Или воспользуйтесь поиском по форуму:
|