c# - 合并列表的最小和

Question

给定一个正整数(0 到 1000 之间)的列表 A(大小 N)，您必须通过一次对 2 个元素求和并添加先前的结果来合并列表的所有元素。

例如，O = { P, Q, R }，可以用 3 种不同的方式合并:

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])相加，我们可以合并 < strong>[40,50] 旨在降低成本。

解决方案:

• 使用 Priority Queue .
• 通过使用优先队列，我们​​可以动态维护合并文件成本的排序顺序，因此可以降低累积成本。让我们再看一遍前面的例子。

[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。