# 2551. Put Marbles in Bags
###### tags: `leetcode`
## Description
You have k bags. You are given a 0-indexed integer array weights where weights[i] is the weight of the ith 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 ith marble and jth marble are in a bag, then all marbles with an index between the ith and jth 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:

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

- 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 <= k <= weights.length <= 105
1 <= weights[i] <= 109

## Solution
- The problem seems to be hard, but the solution can be generated by intuition of the problem
- When we do the division, the score added is `weights[i] + weights[i+1]`. Therefore, to divide into `k` divisions, we need `k-1` gaps between them.
- Accumulate all the `weights[i]+weights[i+1]`, and we can obtain all the values we need for the maximum and minimum.

k--;
vector<long long> comb;
for (int i = 1; i < weights.size(); i++)
    comb.push_back(weights[i] + weights[i - 1]);
sort(comb.begin(), comb.end());

- To get the value, the maximum is all the combinations of the maximum set, and the minimum is the combinations of the minimum set.

for (int i = 0; i < k; i++)
{
    minAns += comb[i];
    maxAns += *(comb.end() - i - 1);
}

- As the result, the value can be seen.

return maxAns - minAns;