ただのメモ

他の人に見せても良い方のメモ

Competitive Programing Typical 90 Problem day7

Day 7.

This problem is easy game, because i grasp the meaning of binary search.

 

Code is below.

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
#input zone
A.sort()

def Complaint(b):
  l = 0
  r = N
  while r-l > 1:
    mid = (r+l)//2
    if A[mid]<=b:
      l = mid
    else:
      r = mid
  if l == N-1:
    return abs(b-A[l])
  else:
    return min(abs(b-A[l]),abs(A[l+1]-b))


for _ in range(Q):
  b = int(input())
  print(Complaint(b))
  • 絶対値が一番小さなところを探す問題。
  • 全部のAの要素を昇順にそろえる。
  • そして、そろえた配列の上を、気になるBの要素との大小比較で二分探索
  • それをBの要素全てでする。
  • また、今回出てきた、2分探索と関連する考え方として、枝分かれがある。
    • 二分探索では、if文で、条件を満たせば、片方を動かし、否なら、他方を動かす。
    • これを右と左に行く、ということと同一視出来る。
    • これは、2分木を用いて表せそう。
      • データ構造としての木
      • そして、そこでの2本の枝分かれ
  • 二分探索と木、を組み合わせた、二分探索木というものがある。こちらを見つつ、こちらを参考にして、お絵描きする。
    • 二分探索木は、二分木で、左の部分木の任意の値<=親<=右の部分木の任意の値、という制約があるもの
import random
class Node:
  def __init__(selfdata):
    self.data = data
    self.left = None
    self.right = None

class BinarySearchTree:
  def __init__(selfarray):
    self.root = None
    for node in array:
      self.insert(node)

  def insert(selfdata):
    n = self.root
    if n == None:
      self.root = Node(data)
      return
    else:
      while True:
        entry = n.data
        if data < entry:
          if n.left is None:
            n.left = Node(data)
            return
          n = n.left
        elif data > entry:
          if n.right is None:
            n.right = Node(data)
            return
          n = n.right
        else:
          n.data = data
          return

  def search(selfsearch):
    n = self.root 
    if n is None:
      return None
    else:
      while True:
        if n.data == search:
          return True
        else:
          if n.data > search:
            if n.left is None:
              return False
            else:
              n = n.left
          else:
            if n.right is None:
              return False
            else:
              n = n.right
      return False


Array = list(range(22))
random.shuffle(Array)
tree = BinarySearchTree(Array)
tree.search(21)

木の可視化はまたの機会としよう。

Classを使って書くコードは構造立っていて、気持ちがいい。

バイバイ!