#c #algorithm #data-structures #binary-search-tree
Вопрос:
У меня возникли некоторые проблемы с этой проблемой, вот краткое изложение проблемы:
- Человек создает блины разного веса.
- После создания блина он будет вставлен в стопку блинов в порядке убывания веса снизу вверх.
- Все блины имеют вес > 0 и уникальны.
Человек хочет поднять стопку блинов с минимальным весом w в граммы. Требование состоит в том, что он должен поднять как можно меньше блинов.
Пример: 5 блинов, созданных по порядку: 11 г, 15 г, 19 г, 1 г, 3g. Они будут сложены от самых тяжелых до самых легких снизу вверх. Если человек хочет поднять хотя бы 5 г, он должен поднять стопку блинов 11 г, 3 г и 1 г, так как это минимальная стопка блинов, которая составляет >5 г.
Функция, которую я должен придумать, minimumWeight(int n) возвращает вес блина в стопке таким образом, чтобы все блины, указанные выше и включающие себя, имели вес не менее n граммов при минимальном количестве блинов. Любая обработка ошибок тривиальна и может быть легко выполнена. Следовательно, для приведенного выше примера minimumWeight(5) будет возвращено 11.
Я не ищу коды, а скорее идею подойти к этому с использованием деревьев AVL.
Скелетный код, который мне дали, представляет собой самобалансирующийся BST, и, кроме того, каждый узел хранит сумму всех узлов в своем поддереве, включая его самого. Я не вынужден использовать BST, но, поскольку тестовые случаи достигают огромных чисел, решение O(n) с использованием массива не сработает.
Заранее большое вам спасибо!
Комментарии:
1. Я не совсем понимаю ваш вопрос… Будет ли список блинов всегда начинаться сверху стопки? например,ответ для 5g-это {1g,3g, 11g}, а не {11g}, не так ли?
2. функция возвращает только самый нижний блин из подсумка, так что сумма весов этого блина и всех блинов над ним больше или равна определенному весу. Таким образом, ответ для 5g возвращает 11 вместо {11,3,1}.
3. Дерево будет работать, но сохранение суммы весов будет довольно медленным, так как вам придется пересчитывать сумму для каждого узла при каждой вставке. Почему бы просто не использовать дерево весов, а затем выполнить обход по порядку, суммируя веса по ходу и возвращая вес узла, когда ваш вес поиска превышен?
4. @DavidC.Rankin это ограничение, заданное набором задач, поскольку мне не разрешено редактировать атрибуты класса. Я думал о обходе по порядку, но сохранение суммы весов будет означать, что код не будет работать, если мне придется пройти дальше корня дерева вправо.