b_예산_2512

문제

if 모든요청이 다 ㄱㅊ > 모두다 요청한대로
else 특정한 정수상한액 설정 그이상이면 상한액 이하면 요청한대로

입력
지방수
요청수들
총예슨

답

이진탐색냄새가 솔솔난다.먼가 딱 맞지않으면 이진탐색이다.(내생각에) 역시 맞음ㅋ

import sys
sys.stdin.readline()
cities = list(map(int,sys.stdin.readline().strip().split()))
budget = int(sys.stdin.readline().strip())
cities.sort(reverse=True)

def set_limit(start,end):
    if start > end:
        return end
    # 정렬된 
    mid = (start+end)//2
    b_sum = 0
    for b in cities:
        if b>mid:
            b_sum+=mid
        else:
            b_sum+=b
    if b_sum == budget:
        return mid
    elif b_sum > budget:
        # 소요되는 금액이 예산보다많음
        return set_limit(start,mid-1)
    else: 
        return set_limit(mid+1,end)

requires = sum(cities)
if budget >= requires:
    print(cities[0])
else:
    ans = set_limit(0,cities[0])
    # 상한선 필요
    print(ans)