[BOJ]白駿1449号水利攻航勝(Python)

3647 ワード
白駿 boj python greedy algorithm Sort テキストリンク

質問する


恒勝は品質の悪い水道会社の修理工です.恒勝は三俊地下鉄の工事が水漏れしたと聞いて、修理に行った.
不思議なことに、パイプから水が漏れているところは一番左の整数しか漏れていません.
恒勝には長さLのテープが無限にある.
恒勝はテープで水を塞ぎたい.恒勝はいつも、水を塞ぐときは、少なくともその位置の左右0.5の距離を与えてこそ、水が漏れないと考えている.
漏水箇所の位置およびテープの長さLを一定に保つために必要なテープの最小数を求めるプログラムを作成する.カットはできませんし、重ねて貼ることもできます.

入力

  • の第1行は、漏水箇所の個数Nおよびテープの長さLを与える.
  • 列目は、漏水箇所の位置を示す.
  • NおよびLは1000以下の自然水であり、漏水箇所の位置は1000以下の自然水である.

    • しゅつりょく

  • の最初の行の出力には、一定のテープ数が必要です.

    • 例


    入力します。

    4 2
1 2 100 101

    出力します。

    2

    に答える

    import sys
from collections import deque

n, l = map(int, sys.stdin.readline().split())
leak = list(map(int, sys.stdin.readline().split()))

leak = deque(sorted(leak))

num = 0

while leak:
    start = leak.popleft()
    num += 1

    while leak and leak[0] - start < l:
        leak.popleft()

print(num)
    簡単です.
    入力を受けてキューにし,sortを用いて水漏れ箇所をソートする.
    また、各pop()の水漏れ箇所間の距離はl - 1以下であり、1つのテープで仕切ることができる.理由は質問に左右各0.5の余地を与えることです.
    ドアにifドアではないwhileドアを入れる理由は、テープで2つの穴を塞ぐだけでなく、距離が十分であれば3つ以上塞ぐことができるからです.
    CSS Flexbox
    Closure in Swift