水利攻航勝(1449)

6390 ワード
白駿 テキストリンク

Greedy


質問する


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

入力


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

しゅつりょく


1行目は、一定リットルに必要なテープの個数を出力します.
import sys

n, l = map(int, sys.stdin.readline().split())
hole = list(map(int, sys.stdin.readline().split()))
hole.sort()
count = 1
tape = hole[0] + (l - 1)

for i in range(1, n):
    if hole[i] <= tape:
        continue
    count += 1
    tape = hole[i] + (l - 1)
    
print(count)

import sys

n, l = map(int, sys.stdin.readline().split())
hole = list(map(int, sys.stdin.readline().split()))
hole.sort()
count = 0
tape = 0

for i in range(n):
    if hole[i] <= tape:
        continue
    count += 1
    tape = hole[i] + (l - 1)
    
print(count)
1)continueに対する感覚が少し足りない.
2)並べ替えが必要な問題=>並べ替えが必要
TIL 14週目4日目導入実践(1)EC 2(サーバ導入)
[OSAM]DART言語ベース(8)Class[#3]継承