第9週#2512予算

💬問題を理解する

コア)共通の上限を獲得した後、規定の総額以下でできるだけ最大の総予算を獲得する.

:
1)すべてのリクエストが割り当てられる場合は、要求に応じて金額を割り当てます.
2)すべての要求が割り当てられない場合、特定の整数上限が計算され、上限を超える予算要求に上限が割り当てられます.上限額以下の予算要求については、要求された金額で配分します.

例
国家予算総額は485
4つの地方の予算要求はそれぞれ120、110、140、150である.
上記を127に限定すると、上記の要求に対してそれぞれ120、110、127、127を手配する.
その和は484であり,可能な最大値となる.
入力条件
1行目には、地方数を表す整数Nが与えられる.Nは3以上10000以下である.次の行は、各地方の予算要求を表すN個の整数を与え、その間にスペースを隔てている.これらの価格はいずれも1以上100000以下です.次の行は、総予算を表す整数Mを与える.MはN以上10000000以下である.
入力例
4
120 110 140 150
485
出力例
127

💡 初志

1.「条件に最適な値を探します.
2.可能な予算範囲は10000000で、非常に広い
Parametic Searchが利用できるようになりました!
関連する使用例はもちを炒めるである.

📝 スケッチの解決

このようにバイナリ検索で最適な上限を探せばいい!

より低い最適上限:

最適上限以上:予算総額に上限を反映する

この予算の合計は、指定された予算の合計以下ですが、最大値を取ります.

イニシャルコード

# 데이터 입력
n = int(input())
departments = list(map(int, input().split()))
budget = int(input())


# 상한액을 찾는 이진탐색
def binary_search(array, start, mid, end) :
  while (start <= end) :
    total = 0
    mid = (start+end) // 2
    for x in array :
      # 상한액을 정했을때 총 예산 계산
      if x > mid :
        total += x - mid
      if total < m :
        end = mid - 1
      else :
        result = mid
        start = mid + 1
  return result

# 상한액을 바탕으로 최종 예산 계산
def calc_budget(upper_limit, departments) :
  total_budget = 0
  for i in departments :
    if i > upper_limit :
      total_budget += upper_limit
    else :
      total_budget += i
  return total_budget



# 모든 요청이 배정될 수 있는 경우 그대로 출력하고 끝남
departments_add = sum(departments)
if departments_add <= budget :
  print(departments_add)
else :
  # 이진탐색 준비
  start = 0
  end = max(departments)
  mid = (start+end)//2
  # 상한액 이진탐색으로 구하기
  upper_limit = binary_search(departments, start, mid, end) 
  # 상한액을 바탕으로 최종 예산 계산
  res = calc_budget(upper_limit, departments) 
  print(res)