救命ボート

質問する

me

faillog

from collections import deque
def solution(people, limit):
    answer = 0
    people.sort()
    boats=deque()
    cnt=0
    for p in range(len(people)-1,-1,-1): # sort reverse 안쓰려고 뒤에서부터 index함
        isFit=0
        while isFit < len(boats): # 배 몇개 검사했는지 확인
            if people[p] <= boats[0]: # 보트 남은 무게보다 작을 경우 태울 수 있음
                cnt+=1
                isFit="done"
                boats.popleft()
                break
            else: # 태울 수 없음
                isFit+=1
                boats.rotate(-1) # 맨 앞을 맨 뒤로 보냄
        if isFit!="done" : # done이 아니라면 들어갈 곳이 없었으니 보트 하나 만들어주기
            if limit-people[p]+people[0]>limit: # 그 값이 너무 커서 가장 작은 값이 들어가도 limit을 넘친다면
                cnt+=1
            else: boats.append(limit-people[p]) # 태우고 남은 무게
    return len(boats)+cnt

効率が通らない.消耗できるものは全部出したと思ってたけど...

solutions

def solution(people, limit):
    answer = 0
    people.sort()
    left = 0
    right = len(people) - 1
    while left < right:
        if people[left] + people[right] <= limit:
            left += 1
            right -= 1
        else:
            right -= 1
        answer += 1
    if left == right:
        answer += 1

    return answer

1つの解決策はpopではなく,左,右変数を用いて残りの最も軽い人と最も重い人を示すことである.
個人昇順ソート
左は0、右はlen(people)-1の値を初期値とします.
残りの人の中で、一番重い人と一番軽い人の重さの和、
3-1制限値未満の場合は、左に1を加算し、右に1を減算します.
3-2 limitより大きい場合は、右に1を減らします.
左が右より小さくなるまで3つ目のプロセスを繰り返し、繰り返すたびに答えに1を加えます.
繰り返し完了後、左から右へ
5-1であれば、残りの1人は、答えに1を加えます.
5-2左>右、全員が船で離れた後、回答に従います