📖 質問する

📝 解法

は、まず岩石を出発点に近い順に並べ、次いで二分探索により最適値を探す方法を選択した.

二分探索の過程で,各点間の距離を調べる際に線形法を用いた.<−岩はせいぜい50000元もあるのでタイムアウトはありません.

得たい値:岩を除去し、各点間の距離の最大値

.

各点間の距離の最値は距離(始点から終点)であるため、二分探索のために開始値を0、終了値を距離とする.

分の探索の過程で,各地点間の距離を含むリストdistsを巡視した.

これまで、除去石の合併距離がmより小さい場合、除去石

mより大きい場合は、石を取り除くのではなく、現在の石から距離を再計算します(合わせた距離=0)
2-1. もしこの時石を取り除く必要があるならば、しかしもう石を取り除く回数がありませんか?
       -> mが最高値になる仮定に矛盾が生じた!!mの値を減算します.
2-2. 石も所望の回数で取り除かれ、mが最高値である条件を満たすとしたら?
       -> 正解の候補になる可能性があるので,正解を変数に入れてm値を上げる.

パスワード

def solution(distance, rocks, n):
    # 바위들이 있는 위치가 출발지점으로부터 가까운 것 순으로 정렬한다.
    rocks.sort()
    
    # 출발지점, 도착지점, 바위 간의 거리를 담는 리스트 dists 구성
    # dist[i] : i ~ i+1 사이 거리
    dists = []
    for i in range(len(rocks) + 1):
        # 출발지점 ~ 첫 바위 사이 거리
        if i == 0 : 
            dists.append(rocks[i])
        # 마지막 바위 ~ 도착지점 사이 거리
        elif i == len(rocks):
            dists.append(distance - rocks[i - 1])
        # 바위 간의 거리
        else:
            dists.append(rocks[i] - rocks[i - 1])

    # 이분 탐색을 위한 시작값, 끝값 설정
    i, j = 0, distance

    # 이분 탐색 시작
    # m : 각 지점 사이의 거리의 최솟값
    # tmp_n : 앞으로 제거할 수 있는 돌의 개수
    # tmp_distance : dp~dq 사이 거리 -> m을 넘어가면 새로 초기화
    # isOk : m이 조건을 만족하는지 여부를 담는 변수
    while i <= j:
        m = (i + j) // 2
        tmp_n = n
        tmp_distance = dists[0]
        isOk = True
        
        # 각 지점 사이의 거리를 담은 list 순회
        for d in range(1, len(dists)):
            # 현재까지 돌을 제거하면서 합쳐진 거리가 m보다 작으면 -> 돌을 제거해야하는 상황
            if tmp_distance < m:
                # 돌을 제거하는 횟수가 안남았다면
                if tmp_n == 0:
                    isOk = False
                    break
                # d - 1번째 돌과 d번째 돌 사이에 있는 바위 삭제
                tmp_n -= 1
                tmp_distance += dists[d]
            else:
                # tmp_distance를 d번째 돌 ~ d+1번째 돌(혹은 끝) 사이 거리로 초기화해준다.
                tmp_distance = dists[d]
                
        # m이 각 지점 사이의 최솟값이라는 것을 만족한다면
        if isOk:
            answer = m # 일단 정답에 넣어놓고
            i = m + 1 # 좀 더 큰 수가 또 각 지점 사이의 최솟값이 될 수 있는지 확인
        else:
            j = m - 1           
    return answer

に感銘を与える

私は探索しながら、一つの岩と今の岩の間の距離を求めて、頭が砕けそうになったので、早めに各場所の間の距離を単独で1枚並べて問題を解いて、大部分の人は時間通りに距離を計算して問題を解いた.本当にそれらのコードを見て、私の説明はずっと複雑だと思います.😢私は割ったものを貼り直して計算しましたが、他の人は貼り付けたものをインデックスだけ移動して計算しました.
また、isokという新しい変数を作成して、石を除去する必要がある場合を処理し、石の除去回数が足りない場合を回避しました.他の人はまず最高値を満たすことに集中し、最高値を満たすためにできるだけ石を除去し、最後に除去した岩の個数がnより大きいかnより小さいかを判断し、m値を更新した.うん.要するに、(石除去回数+最高値)を同時に考えたいのですが、他の人は(最高値)しか考えていないので、後者の方が思い出しやすく、コードもきれいで簡潔です.演算は私のコードより少し多いですが...時間の複雑さに影響しないので、ほほほ.ははは….
最近、私は問題の条件を満たすことに執着しています.他の人よりも、問題の解決が複雑だと思います.問題をあまり近くに見ないで、まず遠くから見て、私がもっと答えやすい方向を考えてみましょう.