Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part4-

Introduction

Hello. It's chewy and chewy. We will solve the introduction to AOJ's algorithms and data structures. It's easy to keep a record of what you've learned.

It's been less than half a year since I started programming myself AtCoder is green, so I'm not a strong man. Let's work hard together.

Pacho Fasomacho Pasomacho Paso

table of contents

This time PART3: Basic data structure. I want to do my best and do it to the end.

ALDS1_4_A: Linear Search ALDS1_4_B: Binary Search ALDS1_4_C: Dictionary ALDS1_4_D : Areas on the Cross-Section Diagram

ALDS1_4_A: Linear Search

Check each element of t Computational complexity is 0 (n * q)

n = int(input())
s = list(map(int,input().split()))
q = int(input())
t = list(map(int,input().split()))
ans = 0
for t1 in t:
    if t1 in s:
        ans += 1

print(ans)

ALDS1_4_B: Binary Search Check each element of t The amount of calculation is 0 (n * q) → 0 (10 ** 9), so it is impossible to do so, so it is 0 (q * ln (n)) in the binary search. Binary search

def b_search(x, target):
    found = False
    min = 0
    max = len(x)
    mid = (min + max) // 2
    while min <= max:
        if target == x[mid]:
            found = True
            break
        elif target > x[mid]:
            min = mid + 1
        else:
            max = mid - 1
        mid = (min + max) // 2
    if found:
        return True
    else:
        return False


n = int(input())
s = sorted(list(set(map(int,input().split()))))
q = int(input())
t = list(map(int,input().split()))
ans = 0
for i in t:
    if  b_search(s, i):
        ans += 1
print(ans)

ALDS1_4_C: Dictionary

Basically calculated with deque

n = int(input())
d = {}

for i in range(n):
    demand, str_list = map(str,input().split())
    if demand == "insert":
        d[str_list] = True

    else:
        if str_list in d:
            print("yes")
        else:
            print("no")

ALDS1_3_D : Areas on the Cross-Section Diagram

Fixed binary search Create a function that can be cleared with a certain value The rest is the flow of the binary search

n,k = map(int,input().split())
w = list(int(input())for i  in range(n))
def amount(p):
    e_amount = 0
    track = 1
    for i in w:
        if i > p:
            return False
        elif e_amount + i > p:
            e_amount = i
            track += 1
        else:
            e_amount += i

    if track <= k:
        return True
    else:
        return False


ng = 0
ok = 10**10
while ng + 1 < ok :
    mid = (ok+ng)//2
    if amount(mid) :
        ok = mid
    else:
        ng = mid

print(ok)

in conclusion

I will do my best