Вы уверены, что вы нашли контрпримеры?Моя математика может быть неправильной, но кажется, что невозможно составить такой список.Заметим, что для списка из трех элементов a <= b <= c мы можем разделить их следующим образом: [a, b], [c].Это потому, что для a + b, чтобы быть больше, чем 2/3 от суммы, у нас было бы (a + b) * 3 > 2 * (a + b + c) или a + b > 2 * c, что означает, что a и / или b должно быть больше, чем c.
Имея это в виду, мы группируем наши числа в три ячейки, каждая из которых такова, что ее сумма меньше N/2.Обратите внимание, что если бы у нас было четыре элемента a <= b <= c <= d, мы могли бы разделить их как [a, b], [c], [d].Повторяя логику, как и раньше, для a + b, чтобы быть больше, чем N/2, нам понадобится (a + b) * 2 > (a + b + c + d) или a + b > c + d, что означает, что a и / или b должно быть больше, чем c.
Мы можем бесконечно повторять эту логику отсюда.Принимая наш список за x, чтобы a + b был больше N/2, нам понадобится (a + b) * 2 > sum(x), что невозможно для списка с 2 или большим количеством элементов больше, чем a и b (что относится ко всем спискам длиной 4 и более).
Применяя эту рекурсивную логику, мы можем построить путь от n бинов до трех бинов, обработать их как числа a, b, c из первого абзаца и построить наш ответ таким образом.
Алгоритмически создайте группу узлов, содержащих каждый элемент в массиве (как список длины один) и сумму (на данный момент равную самому элементу).Вставьте их в кучу мин, с суммой в качестве ключа.Поместите мин два, объедините их (объедините списки элементов, добавьте суммы) и вставьте обратно в кучу мин.Промойте и повторяйте, пока у вас есть два узла в куче.Теперь они содержат ваше решение.