put-marbles-in-bags

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You have <code>k</code> bags. You are given a 0-indexed integer array <code>weights</code> where <code>weights[i]</code> is the weight of the <code>ith</code> marble. You are also given the integer <code>k.</code>

Divide the marbles into the <code>k</code> bags according to the following rules:

<ul>
	<li>No bag is empty.</li>
	<li>If the <code>ith</code> marble and <code>jth</code> marble are in a bag, then all marbles with an index between the <code>ith</code> and <code>jth</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>

The score after distributing the marbles is the sum of the costs of all the <code>k</code> bags.

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

&nbsp;
Example 1:

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

Example 2:

<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= k &lt;= weights.length &lt;= 105</code></li>
	<li><code>1 &lt;= weights[i] &lt;= 109</code></li>
</ul>

putMarbles

Put Marbles in Bags

Greedy

Array

Sorting

Heap (Priority Queue)

你有&nbsp;<code>k</code>&nbsp;个背包。给你一个下标从 0&nbsp;开始的整数数组&nbsp;<code>weights</code>&nbsp;，其中&nbsp;<code>weights[i]</code>&nbsp;是第&nbsp;<code>i</code>&nbsp;个珠子的重量。同时给你整数 <code>k</code>&nbsp;。

请你按照如下规则将所有的珠子放进&nbsp;<code>k</code>&nbsp;个背包。

<ul>
	<li>没有背包是空的。</li>
	<li>如果第&nbsp;<code>i</code>&nbsp;个珠子和第&nbsp;<code>j</code>&nbsp;个珠子在同一个背包里，那么下标在&nbsp;<code>i</code>&nbsp;到&nbsp;<code>j</code>&nbsp;之间的所有珠子都必须在这同一个背包中。</li>
	<li>如果一个背包有下标从&nbsp;<code>i</code>&nbsp;到&nbsp;<code>j</code>&nbsp;的所有珠子，那么这个背包的价格是&nbsp;<code>weights[i] + weights[j]</code>&nbsp;。</li>
</ul>

一个珠子分配方案的 分数&nbsp;是所有 <code>k</code>&nbsp;个背包的价格之和。

请你返回所有分配方案中，最大分数&nbsp;与 最小分数&nbsp;的 差值&nbsp;为多少。

&nbsp;

示例 1：

<pre>输入：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 。
</pre>

示例 2：

<pre>输入：weights = [1, 3], k = 2
输出：0
解释：唯一的分配方案为 [1],[3] 。
最大最小得分相等，所以返回 0 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= k &lt;= weights.length &lt;= 105</code></li>
	<li><code>1 &lt;= weights[i] &lt;= 109</code></li>
</ul>