Наименьшая сумма списка слияния

Question

Учитывая список A (размер N) с положительным целым числом (от 0 до 1000), вы должны объединить все элементы списка, суммируя по 2 элемента за раз и добавляя предыдущий результат.

Например, O = {P, Q, R} можно объединить тремя различными способами:

1. сначала объединить P с Q, а затем объединить результат с R
2. сначала объединить P с R, затем объединить результат с Q
3. сначала объединить R с Q, а затем объединить результат с P

Вы должны найти наименьшую суммутребуется объединить список и вернуть его.

Например, A = {100, 250, 1000}, 3 возможных стратегии слияния:

1. объединить P с Q: 350;результат с R: 1350;итого: 1700
2. слияние P с R: 1100;результат с R: 1350;итого: 2450
3. слияние P с Q: 1250;результат с R: 1350;итого: 2600

Наименьшая сумма - 1700.

Чтобы решить эту проблему, мой подход заключался в том, что, если логически отсортировать список и сначала просто добавить наименьшие элементы, он должен вернутьправильный результат:

    public static int Solution(int[] A)
    {
        if (A.Length < 2)
            return 0;

        var max = 0;
        Array.Sort(A);
        var current = A[0];
        for(var i = 1; i<A.Length; i++)
        {
            current += A[i];
            max += current;
        }

        return max;
    }

Есть идеи?

Изменить: Это была онлайн-оценка, которая была отклонена без какого-либо ответа, я просто пытаюсь улучшить себя и понять, почему это не так

Answer 1

Сбой из-за того факта, что стоимость слияния 2 элементов всегда складывается в совокупную стоимость, если порядок сортировки количества слияния равен не поддерживается .

Например,-

[20,40,40,50]

• Здесь давайте пойдем со слиянием согласно вашему порядку сортировки.
• Слияние [20,40] .Текущая стоимость = 60 .Новый массив = [60,40,50] .
• Слияние [60,40] .Текущая стоимость = 160 (60 + 100) .Новый массив = [100,50] .
• Слияние [100,50] .Текущая стоимость = 310 (160 + 150) .Новый массив = [150] .

Следовательно, общая стоимость составляет 310 .

Как видите,60 было добавлено на неправильной стадии (на [60,40,50] ) во время слияния, где мы могли бы иметь слияние [40,50] с целью снижения затрат,

Решение:

• Использование Приоритетной очереди .
• Используя Приоритетную очередь, мы поддерживаем сортировкупорядок стоимости объединенных файлов динамически и, следовательно, может привести к снижению совокупной стоимости.Давайте снова пройдемся по предыдущему примеру.

[20,40,40,50]

• Слияние [20,40] .Текущая стоимость = 60 .Новый массив = [40,50,60] . (60 идет назад, когда мы вставляем его в приоритетную очередь).
• Слияние [40,50] .Текущая стоимость = 150 (60 + 90) .Новый массив = [90,60] .
• Слияние [90,60] .Текущая стоимость = 300 (150 + 150) .Новый массив = [150] .

Следовательно, общая стоимость составляет 300 , что на 10 меньше стоимости, получаемой с помощью статической сортировкипорядок.