Binary Search
class Solution:
def maxProfit(self, A: List[int], orders: int) -> int:
""" tc O(Nlg(10**9)) sc O(1)
1. find the minimun threashold that meet orders (> orders, not >=)
2. use the max threashold to cacucalte amount of used orders that can be sold (up to threashold +1)
3. caculate revenue
4. if there are still remaining orders need to subtract, it will be at the price of threashold
5. caculate the extra revenue
"""
M = 10**9+7
def cnt_order(thr):
cnt = 0#,val = 0,0
for a in A:
#if a > thr:
x = a-thr+1 # amount thr to a
cnt += max(a-thr,0)
if cnt > orders:
return True
#val = (val+ (a+thr)*x//2)%M
return False #[cnt,val]
l,r = 0, 10**9+1
while l < r:
mid = l + (r-l)//2
if cnt_order(mid):#cnt_order(mid)[0] >= orders:
l = mid+1 # use l = mid, r = mid-1 will TLE
else:
r = mid
res = 0
for a in A:
if a > l:
res = (res +(a+l+1)*(a-l)//2)%M
orders -= a-(l+1)+1
res = (res +(orders) * l )%M
return res