Package g2501_2600.s2551_put_marbles_in_bags

Class Solution

java.lang.Object

g2501_2600.s2551_put_marbles_in_bags.Solution

public class Solution
extends Object

2551 - Put Marbles in Bags.<p>Hard</p> <p>You have <code>k</code> bags. You are given a <strong>0-indexed</strong> integer array <code>weights</code> where <code>weights[i]</code> is the weight of the <code>i^th</code> marble. You are also given the integer <code>k.</code></p> <p>Divide the marbles into the <code>k</code> bags according to the following rules:</p> <ul> <li>No bag is empty.</li> <li>If the <code>i^th</code> marble and <code>j^th</code> marble are in a bag, then all marbles with an index between the <code>i^th</code> and <code>j^th</code> indices should also be in that same bag.</li> <li>If a bag consists of all the marbles with an index from <code>i</code> to <code>j</code> inclusively, then the cost of the bag is <code>weights[i] + weights[j]</code>.</li> </ul> <p>The <strong>score</strong> after distributing the marbles is the sum of the costs of all the <code>k</code> bags.</p> <p>Return <em>the <strong>difference</strong> between the <strong>maximum</strong> and <strong>minimum</strong> scores among marble distributions</em>.</p> <p><strong>Example 1:</strong></p> <p><strong>Input:</strong> weights = [1,3,5,1], k = 2</p> <p><strong>Output:</strong> 4</p> <p><strong>Explanation:</strong></p> <p>The distribution [1],[3,5,1] results in the minimal score of (1+1) + (3+1) = 6.</p> <p>The distribution [1,3],[5,1], results in the maximal score of (1+3) + (5+1) = 10.</p> <p>Thus, we return their difference 10 - 6 = 4.</p> <p><strong>Example 2:</strong></p> <p><strong>Input:</strong> weights = [1, 3], k = 2</p> <p><strong>Output:</strong> 0</p> <p><strong>Explanation:</strong> The only distribution possible is [1],[3]. Since both the maximal and minimal score are the same, we return 0.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>1 <= k <= weights.length <= 10⁵</code></li> <li><code>1 <= weights[i] <= 10⁹</code></li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
long	putMarbles(int[] weights, int k)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

putMarbles

public long putMarbles(int[] weights,
 int k)