K 个元素的最大和

You are given a 0-indexed integer array nums and an integer k. Your task is to perform the following operation exactly k times in order to maximize your score:

1. Select an element m from nums.
2. Remove the selected element m from the array.
3. Add a new element with a value of m + 1 to the array.
4. Increase your score by m.

Return the maximum score you can achieve after performing the operation exactly k times.

 

Example 1:

Input: nums = [1,2,3,4,5], k = 3
Output: 18
Explanation: We need to choose exactly 3 elements from nums to maximize the sum.
For the first iteration, we choose 5. Then sum is 5 and nums = [1,2,3,4,6]
For the second iteration, we choose 6. Then sum is 5 + 6 and nums = [1,2,3,4,7]
For the third iteration, we choose 7. Then sum is 5 + 6 + 7 = 18 and nums = [1,2,3,4,8]
So, we will return 18.
It can be proven, that 18 is the maximum answer that we can achieve.

Example 2:

Input: nums = [5,5,5], k = 2
Output: 11
Explanation: We need to choose exactly 2 elements from nums to maximize the sum.
For the first iteration, we choose 5. Then sum is 5 and nums = [5,5,6]
For the second iteration, we choose 6. Then sum is 5 + 6 = 11 and nums = [5,5,7]
So, we will return 11.
It can be proven, that 11 is the maximum answer that we can achieve.

 

Constraints:

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100
• 1 <= k <= 100

 

/*
 * 思路：
 * 使用Java Stream进行处理
 * 1. 将数组转为一个优先队列进行操作。
 * 2. 每次选择最大的元素，删除并将其加1的新值加入队列。
 * 3. 将选择的元素值累加到得分中。
 */
import java.util.PriorityQueue;
import java.util.Collections;
import java.util.stream.IntStream;

public class MaximizeScoreStream {
    public int maximizeScore(int[] nums, int k) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        IntStream.of(nums).forEach(maxHeap::offer);
        return IntStream.range(0, k)
                        .map(i -> {
                            int max = maxHeap.poll();
                            maxHeap.offer(max + 1);
                            return max;
                        })
                        .sum();
    }
}

题解的整体思路是首先找到数组中的最大值，然后假设每次操作都选择这个最大值进行+1操作，以此来最大化得分。总得分由两部分组成：一部分是k次操作中，每次添加的原最大值之和，即max(nums) * k；另一部分是由于每次操作元素+1带来的额外增加的总和，这部分可以通过求前k个自然数之和得到，即k*(k-1)/2。这种策略假设每次都能顺利地找到当前数组中的最大值并进行操作，忽略了实际操作中数组动态变化带来的复杂性。

O(n)

O(1)