[プログラマー]Lv 2救命ボート

2966 ワード
アルゴリズム#アルゴリズム# プログラマ テキストリンク
リンク:プログラマー-貪欲法>救命ボート

問題の説明


無人島に閉じ込められている人を救命ボートで救い出したい.救命ボートは小さく、1回に最大2人しか乗れず、重量制限もあります.
例えば、人々の体重が[70 kg、50 kg、80 kg、50 kg]であり、救命ボートの重量制限が100 kgであれば、2人目と4人目は一緒に乗ることができるが、1人目と3人目の重量の和が150 kgであるため、救命ボートの重量制限を超えて一緒に乗ることはできない.
できるだけ救命ボートで全員を助けないようにしたい.
特定の人の体重の配列と救命ボートの重量制限をパラメータとして使用する場合は、すべての人を救うために必要な救命ボートの数の最大値を返す解関数を作成します.

せいげんじょうけん

  • 無人島に閉じ込められている人は1人以上50000人以下です.
  • 人の体重は40キロ以上240キロ以下です.
  • 救命ボートの重量は40キロ以下に制限されています.
  • 救命ボートの重量制限は常に人々の体重の中で最も安い価格より大きいため、助けられない人はいません.

    • I/O例


    peoplelimitreturn[70, 50, 80, 50]1003[70, 80, 50]1003

    私の答え

    def solution(people, limit):
    answer = 0    
    people.sort()

    l = 0
    r = len(people) - 1
    
    while l < r:
        if l != r and people[l] + people[r] <= limit:
            l += 1
            answer += 1 
        r -= 1
            
    return len(people) - answer

    説明:

  • を重量順に並べます.
  • は軽者の左index、重者の右indexを指す.
  • 一番重い人と一番軽い人から確認して、二人で乗せます.船の重量制限を超えなければ、重量を指す正確な指数を減らすことで重量を軽減します.(ただし、l!=rでなければならず、l
  • ボートに乗った後、左インデックスを増やし、右インデックスを減らし、次の人を確認します.
  • の戻り値は、回答+{len(人)−(回答*2)}である.
    • 前回問題を解きたい時に考えても解けなかったので、今回は思ったより早く解きました.😮
    Dockerを動かしてみた
    バニラJavaScript私たちのキャンバスの要素を着色🌈