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

📩 -->問題の説明

無人島に閉じ込められている人を救命ボートで救い出したい.救命ボートは小さく、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

💡 ソリューション(使用言語:python)

def solution(people, limit):
    end=len(people)-1
    one=[]
    two=[]
    people.sort()
    for i in range(len(people)):
        while True:
            if people[i]+ people[end]>limit:
                one.append(people[end])
                end-=1
            else:
#                 two.append([i,end,people[i],people[end]])
                two.append(sorted([i,end]))
                end-=1
                break
        if end==0:
            break
    two=list(map(tuple, two))
    return len(set(two))+len(one)

👉 説明:

は基本的に二重ポインタアルゴリズムで問題を解きたい.

インデックスの最初のインデックスと最後のインデックスから変数を設定し、2つのインデックスとlimitを比較し、インデックスの値を追加または減算し、毎回リストに値を追加します.

のいくつかのケースでは、ランタイムプログラムはずっと検索されていましたが、最終的には見つかりませんでした.

なので同じ船に乗っている子供たちにお金をかけずにチェック回数を決めました.

💡 補足ソリューション

def solution(people, limit):
    people.sort()
    answer=0
    start=0
    end=len(people)-1
    while start < end:
        if people[start]+people[end] > limit:
            end-=1
        else:
            start+=1
            end-=1
        answer+=1
        
        if start==end:
            answer+=1
    return answer

法は、前述したように、インデックスの先頭(start)および末尾(end)として二点アルゴリズムを用いた.

2個と乗船回数を増やし(答え)、start=endで同様に追加乗船通過可能!

別の解釈

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

    a = 0
    b = len(people) - 1
    while a < b :
        if people[b] + people[a] <= limit :
            a += 1
            answer += 1
        b -= 1
    return len(people) - answer

は基本的に二重ポインタアルゴリズムで近接しており,ペアリング時の回数のみを求め,全長から減算回数の値を取り戻す.

号で2人しか乗れないので、この人はペアの数を除けば船の数が出てくることを知っているかもしれません...

🌈 に感銘を与える

頑固ではなく、だめだと思ったら、他のコードを書く習慣を身につけなければなりません.もったいないと思わないで!
ソース:プログラマ
間違いがあればメッセージをお願いします🙂