Put Marbles in Bags

You have k bags. You are given a 0-indexed integer array weights where weights[i] is the weight of the i^th marble. You are also given the integer k .

Divide the marbles into the `k` bags according to the following rules:

• No bag is empty.
• If the i^th marble and j^th marble are in a bag, then all marbles with an index between the i^th and j^th indices should also be in that same bag.
• If a bag consists of all the marbles with an index from i to j inclusively, then the cost of the bag is weights[i] + weights[j] .

The score after distributing the marbles is the sum of the costs of all the k bags.

Return the difference between the maximum and minimum scores among marble distributions.

Example 1:

1 Input: weights = [1,3,5,1], k = 2
2 Output: 4
3 Explanation: 
4 The distribution [1],[3,5,1] results in the minimal score of (1+1) + (3+1) = 6. 
5 The distribution [1,3],[5,1], results in the maximal score of (1+3) + (5+1) = 10. 
6 Thus, we return their difference 10 - 6 = 4.

Example 2:

Input: weights = [1, 3], k = 2
Output: 0
Explanation: The only distribution possible is [1],[3]. 
Since both the maximal and minimal score are the same, we return 0.

Constraints:

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

解题思路

　　思维题，罚坐了一个多小时都没写出来。

　　一开始想着用dp，可是无论怎么优化最终的时间复杂度都是$O(n^2)$，而且状态是二维的，别说时间复杂度了空间复杂度就已经爆了，但还是写了一下，当作是练一下dp了。

class Solution {
public:
    long long INF = 0x3f3f3f3f3f3f3f3f;
    
    long long putMarbles(vector<int>& weights, int k) {
        int n = weights.size();
        vector<vector<long long>> f(k + 1, vector<long long>(n + 1, -INF));
        f[0][0] = 0;
        for (int i = 1; i <= k; i++) {
            long long maxf = 0;
            for (int j = i; j <= n; j++) {
                maxf = max(maxf, f[i - 1][j - 1] + weights[j - 1]);
                f[i][j] = maxf + weights[j - 1];
            }
        }
        vector<vector<long long>> g(k + 1, vector<long long>(n + 1, INF));
        g[0][0] = 0;
        for (int i = 1; i <= k; i++) {
            long long minf = 1e18;
            for (int j = i; j <= n; j++) {
                minf = min(minf, g[i - 1][j - 1] + weights[j - 1]);
                g[i][j] = minf + weights[j - 1];
            }
        }
        return f[k][n] - g[k][n];
    }
};

　　然后想着写贪心，结果半天都没想到怎么写。

　　题目等价于把长度为$n$的数组分成连续$k$个子数组，分数是每个子数组的两个端点之和，问最大分数和最小分数的差值。

　　关键是发现这个性质：相邻两个子数组的分界线左右两边的数都必然会同时选。例如如果某个子数组的右端点的下标为$i$，那么下一个子数组的左端点的下标就是$i+1$，那么第$i$个数和第$i+1$个数都必须要同时选。然后发现同时选相邻两个分界线不会影响答案，且选择的分界线与顺序无关：

　　因此可以开个数组存所有的$w[i] + w[i+1]$，然后排序，选择前$k-1$个数求和得到最小值，选择后$k-1$个数求和得到最大值，最后相减得到答案。

　　为什么不选择$w[0]$和$w[n-1]$呢？在求最大值和最小值确实都要加上$w[0]$和$w[n-1]$，但现在问的是差值，因此最后还是会相消，因此不需要加。

　　AC代码如下：

 1 class Solution {
 2 public:
 3     long long putMarbles(vector<int>& weights, int k) {
 4         int n = weights.size();
 5         vector<int> p;
 6         for (int i = 0; i + 1 < n; i++) {
 7             p.push_back(weights[i] + weights[i + 1]);
 8         }
 9         sort(p.begin(), p.end());
10         long long ret = 0;
11         for (int i = 0; i < k - 1; i++) {
12             ret += p[p.size() - 1 - i] - p[i];
13         }
14         return ret;
15     }
16 };

参考资料

　　转化思路 前后缀分解【力扣周赛 330】：https://www.bilibili.com/video/BV1mD4y1E7QK/