Algorithme en Python (dichotomie)

introduction

J'étais libre à cause de l'influence du virus corona ... (Omis ci-dessous) L'arbre Seg précédent étant lourd, je résumerai cette fois la dichotomie qui peut être mise en œuvre relativement facilement.

Façon de penser

Si une limite se rencontre et ne se rencontre pas, vous pouvez rechercher cette limite avec ** O (logN) **. Par exemple, supposons que vous ayez la liste suivante, avec ** x ** pour ceux qui ne remplissent pas les conditions et ** o ** pour ceux qui remplissent. 　　　　　　　　　　　xxxxxxoooooo

Compte tenu de l'indice 0, la dichotomie est efficace lorsque vous souhaitez trouver le 5e ou le 6e (à gauche ou à droite de la limite). Attribuez le côté gauche de la plage de recherche à la ** gauche ** et le côté droit à la variable ** droite **. Ajoutez-les et divisez par 2 (tronqué) comme ** mid ** pour déterminer si l'élément avec l'index ** mid ** remplit les conditions. Si tel est le cas, il n'y a pas de limite à sa droite, alors mettez à jour la valeur de ** right ** à ** mid ** et tronquez le côté droit. Au contraire, s'il n'est pas satisfait, il n'y a pas de limite à gauche de celui-ci, alors mettez à jour la valeur de ** left ** à ** mid **. De cette façon, la section est réduite de moitié à chaque fois, et finalement la recherche se termine lorsque ** droite ** et ** gauche ** sont côte à côte. À ce stade, ** right ** a toujours l'index de l'élément qui satisfait la condition, et ** left ** a l'index de l'élément qui ne satisfait pas, donc dans l'exemple ci-dessus, ** left ** vaut 5, ** right ** a une valeur de 6.

Exemple 1

Dans ** [2, 5, 7, 9, 10, 18, 29] **, considérez le plus petit indice égal ou supérieur à 9. Si la condition est égale ou supérieure à 9, ce sera ** xxxoooo **, qu'elle soit satisfaite ou non, donc la réponse finale est la valeur de ** right **.

code

a = [2, 5, 7, 9, 10, 18, 29]

left = 0
right = len(a) - 1

while right - left > 1:
    mid = (right + left) // 2
    if a[mid] >= 9:
        right = mid
    else:
        left = mid

print(right) # 3

Exemple 2

Puisqu'il s'agit d'un gros problème, résolvez ** Achetez un entier ** de ABC146-C à partir des questions passées d'atcoder. En ce qui concerne les candidats 1 à 10 ^ 9, il existe une limite que vous pouvez acheter du côté gauche et non du côté droit, vous devez donc chercher en deux. Cette fois, nous chercherons directement des entiers au lieu d'index. (Si vous faites une liste, c'est TLE) En guise de mise en garde, si vous ne pouvez pas en acheter un et si vous pouvez tout acheter, il n'y a pas de limite, il semble donc préférable de séparer les boîtiers.

code

import sys

a, b, x = [int(x) for x in input().split()]

left = 1
right = 10**9

if a*right + b*len(str(right)) <= x:
    print(right)
    sys.exit()

if a*left + b*len(str(left)) > x:
    print(0)
    sys.exit()

while right - left > 1:
    mid = (right + left) // 2
    if a*mid + b*len(str(mid)) <= x:
        left = mid
    else:
        right = mid

print(left)

Bissecte standard de la bibliothèque

Il peut être utilisé pour la dichotomie pour déterminer s'il est inclus dans la liste et pour trouver l'index contenant l'élément que vous souhaitez insérer. Vous pouvez le faire vous-même car il y a longtemps fait par vous-même, mais il est normal d'utiliser ** bisect ** de la bibliothèque standard. pense. (Je pense qu'il est nécessaire de s'entraîner à l'utiliser)