budget cuts

🏠
 1 """
 2 time: O(log b * |G|)
 3 space: O(1)
 4 """
 5 
 6 def find_grants_cap(G, b):
 7   comp_total = lambda c: sum(min(c, g) for g in G)
 8   l, r = 0, b
 9   while l < r:
10     m = (l + r) / 2
11     total = comp_total(m)
12     if abs(total - b) < 0.0001:
13       return m
14     else:
15       l, r = ((m, r),(l, m))[total > b]
16 
17 print(find_grants_cap([2, 100, 50, 120, 1000], 190))