Loading...
You are given a list of integers amounts and an even integer k. There are k containers, all initially empty.
You may split each amount in amounts into any number of parts. Each part is a non-negative integer and goes into its own container. A container holds parts of at most one amount, so parts of different amounts never share a container. You may leave any portion of an amount unused, and you may leave any container empty.
After every part is placed, the k / 2 containers holding the most are lost. The safe total is the sum of what the other k / 2 containers hold. If several containers hold the same amount, the tie can be broken in any way. The safe total does not depend on it.
Return the maximum safe total you can achieve.
Input: amounts = [3,5,9,6], k = 4
Output: 9
Explanation: Split the 9 into 4 and 5 and leave the 3 unused, so the four containers hold
5, 4, 5, 6. The two fullest (6 and one of the 5s) are lost, and the other two hold 4 + 5 = 9.
Placing every amount whole gives containers 3, 5, 9, 6, loses 9 and 6, and keeps only 3 + 5 = 8.
Input: amounts = [10,3], k = 2
Output: 5
Explanation: One container is lost and one is safe. Split the 10 into 5 and 5 and leave the 3
unused. One 5 is lost and the other is safe, for a total of 5. Placing 10 and 3 whole instead
loses the 10 and keeps only 3.
Input: amounts = [1,1,1,1], k = 4
Output: 2
Explanation: Place each amount in its own container. Two of the containers are lost, and the
other two hold 1 + 1 = 2.
amounts.length ≤1000k ≤1000k is evenamounts[i] ≤109