Так как скоро вступительный в ШАД решил разобрать задачу 2023 года. Эту задачу вы не найдете в открытом доступе.
Требуется высадить аллею из n деревьев. Лунки под деревьями пронумерованы последовательно. Расстояние между деревьями определяется как разность номеров лунок, где они растут. На Марсе могут выжить только k сортов деревьев. Красота одного дерева i-го сорта c_i.
Требуется озеленить Марс с максимальной суммарной красотой. Однако, деревья одного сорта конфликтуют, поэтому их следует садить как минимум на расстоянии k.
В первой строке находится два целых числа
k (1 <= k <= 5) и n (1 <= n <= 10^5)
В следующей строке следуют k целых чисел c_i (1 <= c_i <= 10^5)
Решение:
Разобьем n деревьев на n/k блоков длины k, и последний блок длины n%k.
Визуально можно представить так: |........|........|........|........|........|....
Заметим что в одном блоке не могут быть двух деревьев одного сорта. Хммм
Ну чтобы у нас не было пустых ячеек мы должны каждую ячейку блока заполнить, следовательно в каждом блоке перестановка ci - тых.
Тогда почему бы не использовать в каждом блоке следующий порядок : с1, c2, ..., ck ?
Потому что последний блок может быть длины < k, а туда нам выгодно расставить максимальные ci-тые.
Тут вы уже должны понять в каком порядке нам сажать....
Давайте отсортруем наш массив по убыванию c, и будем расставлять в каждом блоке c1, c2, .., ck, так мы получим, что в последнем блоке (который может быть длины < k) будет максимальные числа.
Если хотите лучше подготовиться то записывайтесь на наш интенсив.
Благодарю интенсиву в прошлом году много наших студентов успешно поступили в ШАД.
Код в комментариях.