白駿-10816デジタルカード2

1992 ワード
upper_bound bs lowerbound テキストリンク

質問する😀


BSで解題しようとしたが、タイムアウトで解題できなかった.
そこで解法を探す中で下界と上界の概念を見つけた.

コンセプト😃


下限は、初期位置(ターゲットパラメータ以上)を見つけます.
上界は目標数を超える初期位置を探し出す.
もちろん、下界と上界もBSのようにデータを揃えます.
1 2 2 4 5 5 8 10の数列があると言ってください.ここでtargetは5の下限と上限を検索する
  • lower bound
  • 1 2 2 4 5 5 5 5 5 8 10、前からの5番目(リストだと思ったらインデックスが4なら)は5の下限値です.
  • upper bound
  • 1 2 4 5 5 5 5 5 8 10、前から8番目、リストだと思ったらインデックス7の8が上界の値です.
    • 下界と上界はバイナリ探索を少し適用して実現できる.
    BSは、任意のターゲットが見つかった後に戻っても差し支えないアルゴリズムであるが、下付きおよび上付きはstartコードを見て、BSとの違いを見てください.

    コード#コード#😁

    import sys

N = int(sys.stdin.readline().rstrip())
cards = list(map(int, sys.stdin.readline().rstrip().split()))

M = int(sys.stdin.readline().rstrip())
nums = list(map(int, sys.stdin.readline().rstrip().split()))

cards.sort()

def upper_bound(start, end, target):
  while start < end:
    mid = (start + end) // 2
    if target >= cards[mid]:
      start = mid + 1
    else:
      end = mid
  
  return end + 1

def lowr_bound(start, end, target):
  while start < end:
    mid = (start + end) // 2
    if target > cards[mid]:
      start = mid + 1
    else:
      end = mid
    
  return end + 1
for num in nums:
  print(upper_bound(0, len(cards), num) - lowr_bound(0, len(cards), num), end=' ')
    upper boundとlower boundの違いから,if target > cards[mid]:とif target >= cards[mid]:の部分に差があることがわかる.upper_bound는 targetとcards[mid]が同じであっても、start = mid + 1が位置調整を継続していることがわかる.これにより、targetを超える最初のインデックスを求めることができます.
    この問題のエラー部分はendのパラメータで渡された値によってエラーがある.
    適切な値は、upper boundおよびlower boundからlen(cards) - 1に戻るため、endに渡された値がlen(cards)ではなくend + 1に渡されてこそ導出される.

    に感銘を与える🤣

  • low bound,upper boundについて理解しました.
  • は2つの概念を体現しており、もともと頭だけを使いたいと思っていたが、紙に直接書いて、試してみると体現していた.必ず書きながら作ります
    • ［PT - BR］例外である!Dicasパラシュートで降下する人ドミニクexce
    [プログラマー][SQL]JOIN