106.トッポッキ

5641 ワード
アルゴリズム#アルゴリズム# テキストリンク

  • 東彬家の餅は長くない.反対に、一袋入れた餅の全長をカッターで切って合わせます.

  • 餅切り機に高さ(H)を指定すると、一度に一列に切ることができます.
  • の高さがHより大きい餅は、その上のHの部分が切られ、低い餅は切られません.
    • 高さがそれぞれ19、14、10、17センチの餅は、指定されたカッターの高さが15 cmであれば、切った餅の高さは15、14、10、15 cmになります.
    切り餅の長さは4、0、0、2 cmの順です.
    客は長さ6センチを持って行った.
    お客様が
  • に来た場合、Mの全長を必要とする場合は、少なくともMのお菓子を得るためのプログラムを作成して、カッターが設定できる最高高さ値を求めます.

  • 入力条件

  • 1行目には、餅の個数Nと、要求される餅の長さMが与えられる.(1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

  • 2行目は餅の各高さを示した.

  • 餅の高さの総和はいつもM以上で、お客様は必要な量でどれだけの餅を買うことができますか.

  • 高さが10億以下の整数またはゼロです.

  • しゅつりょくじょうけん
  • 少なくともMの餅を持ち帰るために、設定可能な最高高さ値をカッターに出力する.

    • 1.パラメトリック検索

    


n, m = list(map(int, input().split(' ')))
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)

  • パラメトリックメジャー
    :最適化された問題を決定された問題(「はい」または「いいえ」)に変換する解決方法

  • 「必要な条件を満たす最適値を探す問題」では、主にパラメトリック測定が使用されます.

  • 通常、パラメトリック検索タイプはバイナリ検索を使用して解決されます.

  • この問題の解決策は、適切な高さが見つかるまで切断器の高さHを繰り返し調整することである.
  • 「今この高さにカットして条件を満たすことができますか?」確認後、条件の満足度(「はい」または「いいえ」)に応じて検索範囲を縮小して解決できます.

  • カッターの高さ(探索範囲)は1~10億の整数の1つで、このような数を見ると、まずバイナリ探索を考えるべきです.

  • 高さHの探索を探すなら、約31回ですべての状況を考えることができます.
  • の場合、餅の個数はNで最大100万個となるので、バイナリサーチでカッターの高さを変えてH、交換するたびに全ての餅をチェックすると最大3000万回の演算で問題を解くことができます.
    • <カッターの適切な高さHを決定するプロセス>




  • これらのバイナリ探索過程を繰り返すと答えが得られる.
  • のポイントの値は、時間が経つにつれて「最適値」を探します.
    繰り返して得られる餅の長さの和が所望の餅の長さ以上であるたびに、結果値は中間点(mid)に更新される.

  • 現在入手可能なトッポッキの量によって切る位置が決まるので、それを再帰的に実現するのは面倒な作業になるかもしれません.
  • 一般的に、このようなパラメトリック検索問題タイプは、バイナリ検索を再帰的に実現することはなく、重複文実装を用いて問題をより簡潔に解くことができる.
    • IOS objective-c共通コードバックアップレコード
    [白駿4673 Python(python)-セルフサービス番号