Sell Diminishing-Valued Colored Balls[M,Array,Math,Binary Search,Greedy,Sorting,Heap (Priority Queue)]

https://leetcode.com/problems/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)

1. Python

 

class Solution:
    def maxProfit(self, inventory: list[int], orders: int) -> int:
        ans = 0
        # sharnk
        for x in inventory:
            x = x%(10**9 + 7)
        # code
        for x in range(orders):
            intmax = max(inventory)
            ans += intmax
            inventory[inventory.index(intmax)] -= 1
        return ans

 

답은 나오는데, 시간 소요가 커서 fail.. 힌트를 보니 Binary Search를 쓰라고 한다.

 

class Solution:
    def maxProfit(self, inventory: list[int], orders: int) -> int:
        MOD = 10**9+7

        left,right = 0, max(inventory)

        while left < right :
            mid = (left+right)//2
            ans = 0
            for x in inventory :
                ans += max(0,x-mid)
            if ans > orders : left = mid + 1
            else : right = mid
        
        prof = 0
        remain = orders

        for ball in inventory:
            if ball > left:
                sell = ball - left
                if sell >= remain:
                    sell = remain
                remain = remain - sell

                prof += (ball+(ball-sell+1))*sell // 2
                prof %= MOD
        prof += remain*left
        prof %= MOD
        return prof

 

봐도 모르겄다.

 

넘 어려운 친구를 골랐나보다.. 제기랄!!

 

C랑 C++은 당연히 PASS