LeetCode每日一题(2233. Maximum Product After K Increments)

You are given an array of non-negative integers nums and an integer k. In one operation, you may choose any element from nums and increment it by 1.

Return the maximum product of nums after at most k operations. Since the answer may be very large, return it modulo 109 + 7. Note that you should maximize the product before taking the modulo.

Example 1:

Input: nums = [0,4], k = 5
Output: 20

Explanation: Increment the first number 5 times.
Now nums = [5, 4], with a product of 5 * 4 = 20.
It can be shown that 20 is maximum product possible, so we return 20.
Note that there may be other ways to increment nums to have the maximum product.

Example 2:

Input: nums = [6,3,3,2], k = 2
Output: 216

Explanation: Increment the second number 1 time and increment the fourth number 1 time.
Now nums = [6, 4, 3, 3], with a product of 6 _ 4 _ 3 * 3 = 216.
It can be shown that 216 is maximum product possible, so we return 216.
Note that there may be other ways to increment nums to have the maximum product.

Constraints:

• 1 <= nums.length, k <= 105
• 0 <= nums[i] <= 106

---

一句话总结就是每次增加数组中最小的那个数字。之所以要这样做， 我自己的思路是， 每次增加实际对最终答案的贡献是除了当前增加的这个数之外的数组中的其他数的乘积。例如[1, 2, 3, 4, 5], 我增加 1 的话相当于 ans += 2 _ 3 _ 4 _ 5, 增加 2 的话相当与 ans += 1 _ 3 _ 4 _ 5, 增加 3 的话相当与 ans += 1 _ 2 _ 4 * 5, 所以我们要让这个乘积尽可能的大， 自然要把最小的数排除在外， 所以我们只需要每次对数组内最小的数+1 就可以保证最终得到的结果是最大的。

---

use std::cmp::Reverse;
use std::collections::BinaryHeap;

impl Solution {
    pub fn maximum_product(nums: Vec<i32>, mut k: i32) -> i32 {
        let mut heap: BinaryHeap<Reverse<i128>> =
            nums.into_iter().map(|v| Reverse(v as i128)).collect();
        while k > 0 {
            let Reverse(v) = heap.pop().unwrap();
            heap.push(Reverse(v + 1));
            k -= 1;
        }
        let ans = heap.into_iter().fold(1i128, |mut p, Reverse(v)| {
            p *= v;
            p %= 10i128.pow(9) + 7;
            p
        });
        ans as i32
    }
}