題目資訊

• 題目編號: 2551
• 題目連結: Put Marbles in Bags
• 主題: Array, Greedy, Sorting, Heap (Priority Queue)

題目敘述

您有 k 個袋子。給定一個 0-索引 的整數數組 weights，其中 weights[i] 是第 $i$ 顆彈珠的重量。您也被給定一個整數 k.

根據以下規則將彈珠分配到 k 個袋子中：

• 沒有袋子是空的。
• 如果第 $i$ 顆彈珠和第 $j$ 顆彈珠在同一個袋子中，那麼所有索引在 $i$ 和 $j$ 之間的彈珠也應該在相同的袋子中。
• 如果一個袋子包含了索引從 $i$ 到 $j$ 包括在內的所有彈珠，那麼袋子的成本是 weights[i] + weights[j]。

在分配彈珠後的 得分 是所有 k 個袋子成本的總和。

返回 彈珠分配中 最大 和 最小 得分之間的 差異。

範例 1:

輸入: weights = [1,3,5,1], k = 2
輸出: 4
解釋: 
分配 [1],[3,5,1] 得到最小得分 (1+1) + (3+1) = 6。 
分配 [1,3],[5,1] 得到最大得分 (1+3) + (5+1) = 10。 
因此，我們返回它們的差 10 - 6 = 4。

範例 2:

輸入: weights = [1, 3], k = 2
輸出: 0
解釋: 唯一可能的分配是 [1],[3]。 
由於最大得分和最小得分相同，我們返回 0。

約束條件:

• $1 \leq k \leq \text{weights.length} \leq 10^5$
• $1 \leq \text{weights}[i] \leq 10^9$

直覺

本問題要求我們將一組彈珠分配到 k 個袋子中，具備特定限制條件，目的是計算此種分配方式中可能的最大和最小得分之間的差異。這些限制條件確保了在任何選擇的袋子中，彈珠必須是連續的。每個袋子的代價僅取決於其邊界上的彈珠重量，即為其起始和結束索引上彈珠重量的總和。因此，精心選擇每個袋子的邊界彈珠是至關重要的。解決這個問題的一個直觀方法是利用相鄰彈珠的成對和，這些成對和本質上代表了確定袋子起始和結束的潛在點（因此也定義了代價邊界）。

解法

解決方案涉及以下關鍵步驟：

1. 成對和計算：

   • 計算所有連續彈珠重量的總和。若有 n 顆彈珠，則會有 n-1 個和。每個和代表兩個袋子之間的潛在劃分點。

2. 排序：

   • 將這些成對和進行排序。最小的和代表最小的邊界增加，而最大的和代表最大的邊界增加。透過排序可以有效選擇成對和，以最大化或最小化得分。

3. 得分計算：

   • 最大得分計算： 從排序列表中選擇最大的 (k-1) 個和。這些和被加入到得分中，以模擬選擇最大代價劃分。選擇 (k-1) 是基於這樣的事實，即對於 k 個袋子，增加 (k-1) 個有效分割點能改善得分，因為陣列的首尾元素只需依據問題定義計算一次。
   • 最小得分計算： 同樣地，從排序列表中選擇最小的 (k-1) 個和。這種選擇構成一個最小的得分設置，聚焦於分割邊界上的小幅增長。

4. 差異計算：

   • 計算最終結果為上述步驟中計算出的最大得分和最小得分之間的差異。

此方法透過利用連續分割的特性、成對和的排序次序以及邊界的策略性選擇，來有效地計算所需結果。此邏輯確保最大和最小配置都是從同一基礎的潛在分割中導出，最終計得的差異即為在給定限制條件下袋子分配最佳配置的變動程度。

程式碼

C++

class Solution {
public:
    long long putMarbles(vector<int>& weights, int k) {
        int n = weights.size();
        vector<int> splits;

        // 計算相鄰元素的配對和
        for (int i = 0; i < n - 1; i++) {
            splits.emplace_back(weights[i] + weights[i + 1]);
        }

        // 將配對和進行排序
        sort(splits.begin(), splits.end());

        // 透過選擇最大的 (k-1) 個和計算最大分數
        long long maxScore = accumulate(splits.end() - (k - 1), splits.end(), static_cast<long long>(0));

        // 透過選擇最小的 (k-1) 個和計算最小分數
        long long minScore = accumulate(splits.begin(), splits.begin() + (k - 1), static_cast<long long>(0));

        // 返回最大和最小分數之間的差
        return maxScore - minScore;
    }
};

Python

class Solution:
    def putMarbles(self, weights, k):
        n = len(weights)
        splits = []

        # 計算連續元素的配對和
        for i in range(n - 1):
            splits.append(weights[i] + weights[i + 1])

        # 對這些配對的和進行排序
        splits.sort()

        # 透過取最大的 (k-1) 個和來計算最大得分
        maxScore = sum(splits[-(k - 1):])

        # 透過取最小的 (k-1) 個和來計算最小得分
        minScore = sum(splits[:k - 1])

        # 返回最大得分和最小得分的差
        return maxScore - minScore

複雜度分析

• 時間複雜度: $O(n \log n)$
  時間複雜度主要由於對 splits 向量的排序操作所主導，該向量包含 $n - 1$ 個元素。對此向量進行排序需要 $O((n - 1) \log (n - 1))$ 的時間，當 $n$ 較大時，簡化為 $O(n \log n)$。隨後計算 maxScore 和 minScore 的累積操作各需要 $O(k)$ 的時間，其中 $k \leq n$，因此這些操作不影響整體的 $O(n \log n)$ 時間複雜度。

• 空間複雜度: $O(n)$
  空間複雜度由 splits 向量決定，該向量存儲 $n - 1$ 個元素，因此其空間複雜度為 $O(n)$。其他變量如 maxScore 和 minScore 所需的額外空間僅為 $O(1)$。因此，整體空間複雜度為 $O(n)$。