(白駿)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