Leetcode 2551. Put Marbles in Bags

[Woodyiiiiiii]

这道题很有意思！

先列一下感到疑惑、需要突破的条件口：

1. 分割成k份
2. 对于[i,j]的子数组，它的和是左右两端元素之和
3. 求的是最大和与最小和的差

只要充分利用以上所有条件，配上合理的时间复杂度(观察题目参数大小范围)，就可以解题了。

一开始我想用DP，但显然，不满足无后效性。那还有其他做法吗？那只能往排序/PQ方面靠了。

不如从示例出发：

Input: weights = [1,3,5,1], k = 2
Output: 4

从时间复杂度可以窥见一斑。要满足某些增长性，或者说要从每次遍历获得什么，而已知条件特殊的是k，所以可以从k遍历出发，用PQ结合数组，从而实现增长。

画图理解，可以得知当k=n||k==1的时候，结果为0。那么k-1,k-2...2呢，该如何变化？比如示例，一开始k==n时，最大和与最小和都是[1,1],[3,3],[5,5],[1,1]，k减小1后，最大和变成[1,3],[5,5],[1,1]，最小和变成[1,1],[3,5],[1,1]。那么可以发现，每次都是有一个类似子数组合并的过程，即，像链条一样连接nums[i]和nums[i+1]的关系，这个过程模拟了分割取和的情况。

那么最终推导出，将相邻元素排序放入PQ中，从n逐级递减分割，就可以得到结论。

class Solution {
    public long putMarbles(int[] weights, int k) {
        int n = weights.length;
        if (k == 1 || k == n) {
            return 0;
        }
        long total = 0;
        for (int w : weights) {
            total += w;
        }
        PriorityQueue<int[]> mnHeap = new PriorityQueue<>((o1, o2) -> o1[0] + o1[1] - o2[0] - o2[1]);
        PriorityQueue<int[]> mxHeap = new PriorityQueue<>((a, b) -> -(a[0] + a[1] - b[0] - b[1]));
        for (int i = 0; i < n - 1; i++) {
            mxHeap.offer(new int[]{weights[i], weights[i + 1]});
            mnHeap.offer(new int[]{weights[i], weights[i + 1]});
        }
        long mx = total, mn = total;
        for (int i = n - 1; i >= k; i--) {
            int[] max = mxHeap.poll();
            int[] min = mnHeap.poll();
            mn -= max[0] + max[1];
            mx -= min[0] + min[1];
        }
        return mx - mn;
    }
}

Tips：

• 思路是：列出已知有用条件——根据示例——推导/利用条件——明确算法和思路
• 这道题也提供了分割成k份的一种解题思路，就是从k出发，考虑k与k-1的关系，有点像Codeforce的一题其实就是那题codeforce分割成k份的提供给了我思路

---

• 2551. Put Marbles in Bags
• https://leetcode.com/problems/put-marbles-in-bags/solutions/3111736/java-c-python-3-approachs-best-o-n/