Maximum Score From Numbered Balls
A game contains several tubes filled with numbered balls. A tube containing k balls has balls numbered from 1 to k, with ball k at the top.
In each move, a player chooses a non-empty tube and removes its top ball. The player earns points equal to the number printed on that ball.
Find the maximum total score the player can earn by removing exactly the required number of balls.
Implement the following method:
long maximumBallScore(List<Integer> ballCounts, int removalCount)
ballCounts.get(i) is the initial number of balls in the i-th tube.removalCount is the exact number of balls that must be removed.- The method returns the maximum total score that can be earned.
Ball Arrangement
- A tube with
k balls contains balls numbered from 1 to k.
- The ball numbered
k is at the top, followed by k - 1, continuing down to 1.
- Only the top ball of a tube can be removed.
Rules
- Exactly one ball must be removed in each move.
- A ball may be removed only from a non-empty tube.
- The points earned equal the number printed on the removed ball.
- The same tube may be selected in multiple moves.
- Exactly
removalCount balls must be removed in total.
Constraints
1 ≤ ballCounts.size() ≤ 100,000 1 ≤ ballCounts.get(i) ≤ 1,000,000,000 1 ≤ removalCount ≤ 2,000,000,000 removalCount ≤ sum of all values in ballCounts - The result fits in a
long.
- Neither
ballCounts nor any value inside it will be null.
Examples
Example 1
maximumBallScore( ballCounts = List.of(6, 3, 3), removalCount = 5 )
Output: 21
The player can remove balls numbered 6, 5, 4, 3, and 3. The maximum total score is 21.
Example 2
maximumBallScore( ballCounts = List.of(2, 5, 4), removalCount = 7 )
Output: 23
The highest available ball numbers can be removed in the order 5, 4, 4, 3, 3, 2, and 2. Their total is 23.
Example 3
maximumBallScore( ballCounts = List.of(4), removalCount = 4 )
Output: 10
The only tube contains balls numbered 4, 3, 2, and 1 from top to bottom. Removing all of them produces a total score of 10.