(白駿)1449.水利工事

リンク

Python Tip!

map(int, input().split()によりint変換を1行に簡潔に処理できる.リストを直接作成することもできます.

print(「f{variable}」)構文は、JSと同じ効果を提供します.

Greedy問題のため,初めて解く場合,長さを一つ一つ計算するために解1を複雑に編成する.下書き2は映像を参考にして書かれています.最大入力長が1001の値を予め作成しておき、O(N)の時間的複雑さを繰り返す.入力長が1億を超える場合は、他の方法を選択したほうがいいです.

答えを出す。

K, L = map(int, input().split())
holes = list(map(int, input().split()))
holes.sort()

stack = [] # 구멍 stack
n = 0 # 테이프 갯수
need = 0 # 현재 이어지는 길이
start = holes[0]
for i in holes:
  print(f'start = {start}, i = {i}, 길이 = {L}')
  if stack:
    if start + L > i and start - L < i:
      stack.append(i)
      need += 1
    else:
      stack.clear()
      stack.append(i)
      start = i
      need = 1
      n += 1
  else:
    stack.append(i)
    start = i
    need += 1
  
  if need == L:
    stack.clear()
    need = 0;
    n += 1
  
if stack: 
  n += 1
print(n)

説明する。

K, L = map(int, input().split())

coord = [False] * 1001
for i in map(int, input().split()):
  coord[i] = True

ans = 0   
x = 0
while x < 1001:
  if coord[x]:
    ans += 1
    x += L
  else:
    x += 1