2512번 – 예산

문제

https://www.acmicpc.net/problem/2512

풀이

코드

from sys import stdin

def answer():
  global n, arr, money
  if sum(arr) <= money:
    print(max(arr))
    return
  arr = sorted(arr)
  if arr[0]*n >= money:
    print(money//n)
    return
  stackArr, stack = ([], 0)
  for i in range(n):
    stackArr.append(stack+arr[i]*(n-i))
    stack += arr[i]
  
  start, end, index = (0, n-1, 0)
  while(start <= end):
    mid = (start+end)//2
    if stackArr[mid] <= money: start, index = (mid+1, mid)
    else: end = mid-1
  a = money - stackArr[index]
  b = n - (index+1)
  ans = arr[index] + a//b
  print(ans)

n = int(input())
arr = list(map(int, stdin.readline().split()))
money = int(input())
answer()