k стеков уже заполнены числами с диапазоном [0,5].Мне нужно заполнить пустой стек, выталкивая числа из других k стеков и помещая их в этот стек.Мне нужно сделать это так, чтобы сумма квадратов расстояния между всеми соседними числами в этом новом стеке была минимизирована.Обратите внимание, что размер каждого заполненного стека примерно в 100 раз меньше, чем k
Пример: давайте рассмотрим k = 3 заполненных стека, s1 = [1,2], s2 = [3, 4], s3 = [4,5] с их «верхней» частью в крайнем левом углу.Теперь, если я вставлю числа в некоторый пустой стек E = [] из S1, S2, S3 в следующем порядке:
pop s1, pop s1, pop s2, pop s2, pop s3, pop s3
Я получаю E = [5,4,4,3,2,1] с суммой квадрата расстояния для всех соседних чисел = (5-4) ^ 2 + (4-4) ^ 2 + (4-3) ^ 2 + (3-2) ^ 2 + (2-1) ^ 2 = 1 + 0 + 1 + 1 + 1 = 4. Следовательно, его стоимость равна 4, что кажется минимальным, если сделать это в этом конкретном порядке.Следовательно, решение имеет следующий порядок:
(pop s1, pop s1, pop s2, pop s2, pop s3, pop s3)
Мой неправильный подход:
Рассмотримнабор чисел в верхней части k стеков.Найдите минимальное число и поместите его в новый стек.Делайте это несколько раз, пока все стеки не станут пустыми.Используемая структура данных: приоритетная очередь.Сложность времени: O (S * log (k)) где S - размер каждого стека.
У меня есть 2 вопроса.
1. Как вы думаете, какой самый эффективный способ сделать это правильно?2. Какой, по вашему мнению, самый эффективный способ сделать это приблизительно (лучше, чем мой подход с точки зрения правильности)?