Description

Submission

class Solution {
    const int M = 1e9 + 7;
    long long count(int k, vector<int>& inventory) {
        long long ret = 0;
        for(int x: inventory) {
            if(x < k) break;
            ret += x - k + 1;
        }
        return ret;
    }
public:
    int maxProfit(vector<int>& inventory, int orders) {
        sort(inventory.begin(), inventory.end(), greater<int>());

        long long left = 1, right = inventory[0];

        while(left < right) {
            int mid = left + (right - left) / 2;

            if(count(mid, inventory) <= orders) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        long long ret = 0;

        for(long long x: inventory) {
            if(x < left) break;
            ret += (x + left) * (x - left + 1) / 2;
            ret %= M;
        }

        ret += (left - 1) * (orders - count(left, inventory));

        return ret % M;
    }
};

// 2,8,4,10,6

// 10 8 6 4 2
// mid