[Baekjoon][Python]1449号水利攻航勝

1449号補修空港リフト

質問する

に答える

水が漏れているところは詰まっている問題です.今考えると簡単な問題で、想像以上に長い時間をかけて問題を理解します.
問題の条件を一つ一つ見る.

水が漏れているところが不思議なことに、一番左の浄水から遠いところだけ水が漏れています.

長さは無限のLバンドである.

常に水が詰まっている場合は、少なくともその位置の左右0.5の間隔を与えてこそ、水が漏れない.

テープを切ることはできません.テープを重ねて貼ることもできます.

1番の条件のため、3番の条件はあまり意味がありませんが、コードに反映されています.
2、4つ目の条件で考えると、水漏れの箇所を並べて、繰り返しの扉回りに回ります.
最後に、テープを貼り付ける位置が水漏れの位置より小さい場合、テープを貼り付けることとテープを切り取ることができないため、現在の位置-0.5+テープ長の値に加算すると、テープを貼り直す最終位置となります.
これを実現するコードは次のとおりです.(水漏れ箇所は整数値しか存在しないので、左0.5はあまり意味がありません)

import sys

def getTapeCount(leaks, n, l):
    lastTapeLoc = 0
    count = 0
    for i in range(n):
        if leaks[i] > lastTapeLoc:
            lastTapeLoc = leaks[i] - 0.5 + l
            count += 1
    return count

N, L = map(int, sys.stdin.readline().split())

locations = list(map(int, sys.stdin.readline().split()))
locations.sort()

print(getTapeCount(locations, N, L))

n/a.結論

この問題は説明しにくいので、説明したら簡単に解けます.ソートは最も核心的な問題で、その後は簡単な考えだけで解決できます.