https://leetcode.com/problems/sell-diminishing-valued-colored-balls/ from Groupon

Thinking process:

An ituitive way is to always pick a ball from the color with most balls remaining. So, the order will be something like below

We can easily implement this by using a max heap. The time complexity is O(NlogN). However, after looking at the constraint, the orders is at most 10^9, which makes this time complexity infeasible.

Another way to think about this is reverse thinking. We can find the threshold we’ll go to eventually. We’ll pick everything above the threshold, and determine if we still need to pick more based on orders.

We can use binary search to find this threshold. The time complexity for this will be O(LlogL). L is the length of inventory, which is under 10^5, so the LlogL is doable.

Below is the code. After the binary search, the Min will be the maximum number which makes sum <= orders. This is exact what we need. After that, we just need to determine how many do we need at threshold (Min) level.

 1class Solution {
 2public:
 3    typedef unsigned long long ll;
 4    int maxProfit(vector<int>& inventory, int orders) {
 5        int mod = 1e9 + 7;
 6        int Max = 1e9, Min = 0;
 7        while (Max > Min) {
 8            int mid = (Max + Min) / 2;
 9            ll sum = 0;
10            for (auto& n : inventory) {
11                if (n > mid) {
12                    sum += (n - mid);
13                }
14            }
15            if (sum > orders) Min = mid + 1;
16            else Max = mid;
17        }
18        ll sum = 0;
19        for (auto& n : inventory) {
20            if (n > Min) {
21                sum += (ll)(n+Min+1)*(n-Min)/2;
22                orders -= (n - Min);
23            }
24        }
25        sum += (ll)orders*(Min);
26        return sum % mod;
27    }
28};