1
class Solution:
2
    def findBestValue(self, arr: List[int], t: int) -> int:
3
        def getsum(x):
4
            s = 0
5
            for i in range(n):
6
                if arr[i] > x:
7
                    s += x * (n - i)
8
                    break
9
                else:
10
                    s += arr[i]
11
            return s
12

13
        arr.sort()
14
        n = len(arr)
15
        l, r = 0, max(arr)
16
        ans = [inf, inf]
17
        while l <= r:
18
            m = l + (r - l) // 2
19
            if abs(getsum(m) - t) <= ans[0]:
20
                if abs(getsum(m) - t) == ans[0]:
21
                    ans[1] = min(m, ans[1])
22
                else:
23
                    ans = [abs(getsum(m) - t), m]
24
            if getsum(m) > t:
25
                r = m - 1
26
            else:
27
                l = m + 1
28

29
        return ans[1]