LeetCode每日一题(1648. Sell Diminishing-Valued Colored Balls)

You have an inventory of different colored balls, and there is a customer that wants orders balls of any color.

The customer weirdly values the colored balls. Each colored ball’s value is the number of balls of that color you currently have in your inventory. For example, if you own 6 yellow balls, the customer would pay 6 for the first yellow ball. After the transaction, there are only 5 yellow balls left, so the next yellow ball is then valued at 5 (i.e., the value of the balls decreases as you sell more to the customer).

You are given an integer array, inventory, where inventory[i] represents the number of balls of the ith color that you initially own. You are also given an integer orders, which represents the total number of balls that the customer wants. You can sell the balls in any order.

Return the maximum total value that you can attain after selling orders colored balls. As the answer may be too large, return it modulo 109 + 7.

Example 1:

Input: inventory = [2,5], orders = 4
Output: 14

Explanation: Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
The maximum total value is 2 + 5 + 4 + 3 = 14.

Example 2:

Input: inventory = [3,5], orders = 6
Output: 19

Explanation: Sell the 1st color 2 times (3 + 2) and the 2nd color 4 times (5 + 4 + 3 + 2).
The maximum total value is 3 + 2 + 5 + 4 + 3 + 2 = 19.

Constraints:

1 <= inventory.length <= 105
1 <= inventory[i] <= 109
1 <= orders <= min(sum(inventory[i]), 109)

---

这题做到一半就后悔了， 知道自己能做出来，但是各种细节问题也着实折磨了我好一阵。
先说整体思路， 一定有一个价格，使得超过这个价格的球都卖掉可以达到订单数量， 因为球的数量就是价格，所以上面的价格可以直接换成数量。也就是一定存在一个数量，各种颜色的球将多于这个数量的部分拿出来卖掉，获得的收益一定是最大收益。这个数量该怎么确定呢？看看题目的数量级，明摆着是让你二分法来找， 取值范围是从 0 到所有颜色的球的最大数量。将大于这个值的球都卖出可能会导致卖出的数量大于或者小于订单数量， 好在无论是大于或者小于我们只需要用我们找到的这个数量来进行多退少补

---

impl Solution {
    fn profit(high: i64, low: i64) -> i64 {
        (high + low + 1) * (high - low) / 2
    }
    pub fn max_profit(mut inventory: Vec<i32>, orders: i32) -> i32 {
        inventory.sort();
        inventory.reverse();
        let mut high = inventory[0] as i64;
        let mut low = 0;
        while low < high {
            let mid = (low + high) / 2;
            let mut count = 0;
            for i in 0..inventory.len() {
                if inventory[i] as i64 > mid {
                    count += inventory[i] as i64 - mid;
                    continue;
                }
                break;
            }
            if count > orders as i64 {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        let mut total = 0;
        let mut count = 0;
        for i in 0..inventory.len() {
            if inventory[i] as i64 > low {
                total += Solution::profit(inventory[i] as i64, low);
                count += inventory[i] as i64 - low;
                continue;
            }
            break;
        }
        ((total - (count - orders as i64) * low) % (10i64.pow(9) + 7)) as i32
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38