探索バイナリ-例)トッポッキ

4530 ワード
ParametricSearch アルゴリズム#アルゴリズム# バイナリナビゲーション テキストリンク

💬 問題を理解する


コア)カッターで設定できる最高高さを求める.
せめて合わせてMサイズの切り餅を手に入れましょう.
  • 第1行目は、菓子の数N及び要求される菓子の長さMを与える
    (1<=N<=1,000,000 1<=M<=2,000,000,000)
  • 行目は、菓子の個別の高さを与えた.(0<=高さ<=10億)

    • 足画はどうせ私が理解するために描いたのだ.
    なんだ.

    🔍 Parametric Search


    最適化問題を決定問題(yesまたはno)解決方法に変換する
    主に「条件に最適な値を探す」に使用します.
    ex)範囲内で条件を満たす最大値最適化問題等
    ААААААААААААААА\1040
    coteでは、通常、バイナリナビゲーションを使用してパラメータ検索を解決します.

    💡 問題を解く構想.


    「適切な高さが見つかるまでカッターの高さHを繰り返し調整する」
    切断機の高さは1億から10億です.
    こんなにたくさんの空洞風を見て、まず考えなければならないのはバイナリ探索です.
    検証時間の複雑さ
    検索高さH:約31
    トッポッキの数Nは最大100万個までなので、交換するたびに、すべてのトッポッキチェック:31*100万=約3000万回まで計算します
    質問時間制限が2秒なので、タイムアウトのスリルを受けずに正解!

    コード#コード#

    # 떡의갯수 n, 요청한 떡의 길이 m
n, m = list(map(int, input().split(' ')))
# 각 떡의 개별높이 정보 array 
array = list(map(int(input().split())))

# 이진탐색을 위한 시작점, 끝점
start = 0
end = max(array)

# 이진탐색 수행
result = 0

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 # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
    start = mid + 1

print(result)
    データ構造シナリオ、リンクリスト
    dockerのgitlabのバックアップとリカバリ