https://www.acmicpc.net/problem/2805
initial
easy
mid is literally our guess value for the answer. In this question, mid is the min. height value to chop the trees off to reach target.
Now do we return left or left-1 for the answer? I have been confused but now i get it.
Let's look at the relationship between left and mid.
left = mid+1
So in this q, we want to get the min. height, which is mid. So we do mid-1 which effectively is left.
solution
import sys
input = sys.stdin.readline
n, target = map(int,input().split())
lst = list(map(int,input().split()))
lst.sort()
left = 0
right = lst[-1]
while left<=right:
mid = (left+right)//2
tmp=0
for a in lst:
if a>mid:
tmp+=a-mid
if tmp>=target:
left=mid+1
else:
right=mid-1
print(left-1)complexity
log n time and n space complexity
