'''
2020-06-14 풀이
접근
1. 자른 나무의 합은 M값 이상이다.
2. 목재절단기의 높이 H에 따라 M이 달라진다.
3. H의 높이의 최소~최대는 0~max(list_value)다.
4. 목재절단기의 높이를 Binary_Search로 조절해가면서 최소치와 같도록 한다.
** start와 mid가 만나고 한번 더 while이 돌면 end는 start = mid 보다 작게 된다.
** sum_wood를 구하는(갱신하는) 식이 필요하다.
난점
1. 벌목량의 합계를 구해서
→ 최초 벌목량의 합계는 구하기 쉬움. 갱신을 어떻게 할 것인가?
2. 주어진 M과 비교한 뒤
3. 둘의 크기에 따라
4. H의 높이를 조절하는 것.
'''
import sys
n ,m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
start = 1
end = max(a)
while start <= end:
mid = (start + end) // 2
sum_wood = 0
for i in a:
if i >= mid:
sum_wood += i - mid
if sum_wood >= m:
start = mid + 1
else:
end = mid - 1
print(end)```
'''
접근
1. 절단기 높이의 최소/최대치를 각각 변수에 할당한다.
2. 절단기 높이를 변화시킬 때의 수확량을 새로운 변수에 할당한다.
3. 절단기 높이의 최소치 때의 수확량을 lf, 최대치 때의 수확량을 rf로 둔다.
4. mid = (lf + rf) // 2 로 한다.
5. 수확량을 최소요구치와 비교하여 수확량이 더 크면 rf = mid - 1이 된다.
수확량을 최소요구치와 비교하여 수확량이 더 작으면 lf = mid + 1이 된다.
왜 풀지 못했나?
1. 내 방식대로 풀려면 수확량과 H 높이의 관계를 나타내는 함수가 하나 더 필요하다.
이를 만들어서 하려다 보니 제한된 시간(30분)을 초과했다. 이렇게 접근하면 안됐다.
'''
import sys
def sum_wood(H):
li = []
wood = []
for i in a:
li.append(i)
if H == 0:
return sum(li)
elif H != 0:
for j in range(n):
wood.append(a[j] - H)
return sum(wood)
n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
a.sort()
lf = sum_wood(a[-1])
rf = sum_wood(0)
res = 0
while lf <= rf:
mid = (lf + rf) // 2
if m == mid:
res = mid
elif m < mid:
rf = mid - 1
else:
lf = mid + 1
