Résumé de la recherche Bisection pour les professionnels de la concurrence
Quand utiliser
Juger à plusieurs reprises la taille de N éléments
- Lors de la recherche de la valeur maximale / minimale qui satisfait la condition.
- Lors du comptage des éléments qui satisfont aux conditions.
- Lors de la recherche du Kth d'une liste triée. (Nombre de nombres inférieur ou égal au Kème nombre dans la liste <= valeur maximale qui satisfait K)
Ce qui est bon
Normalement, si vous regardez chacun d'eux, vous pouvez raccourcir l'endroit où l'ordre de O (N) est amené à O (log N).
Que faire
- Trier N éléments à l'avance.
- Sélectionnez deux «valeurs externes» aux deux extrémités de tous les éléments triés. (= Si la valeur initiale est définie aux deux extrémités, ce point ne sera pas évalué, donc il sera invalide si tous sont Vrai / Faux)
- Répétez les opérations suivantes pour trouver enfin la limite entre ok qui satisfait la condition et ng qui ne le fait pas.
- Déterminez si la valeur moyenne (point médian) des deux valeurs satisfait la condition, et si elle est satisfaite, définissez ok comme valeur du point médian. S'il n'est pas satisfait, ng est défini comme point médian.
- Terminez l'itération lorsque la différence entre les valeurs absolues de ok et ng est inférieure à 1. (= La limite a été trouvée)
image
En pensant
Quel côté est Vrai / Faux lorsque la liste triée est filtrée selon les conditions.
modèle
Jugement de condition
def is_ok(mid: int):
#Lisez d'abord les éléments qui ne sont pas dans la cible de recherche(S'il s'agit d'un index de liste, il est hors de portée.)
if mid < 0:
return True | False # ※1
elif mid >= N:
return True | False
return True | False #Résultat de la condition de jugement
- 1: Spécifiez le côté gauche de l'état final de la liste.
True ----||---- False→TrueFalse ----||---- True→False
Partie d'exécution de la recherche
def binSearch(ok: int, ng: int):
#print(ok, ng) #Premier état binaire
while abs(ok - ng) > 1: #Condition de fin (lorsque la différence est de 1 et que la limite est trouvée)
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid #Si le milieu remplit les conditions, ça va jusqu'à mi, alors amenez ok au milieu
else:
ng = mid #Si mid ne remplit pas les conditions, ng est à mi-chemin, alors amenez ng au milieu
#print(ok, ng) #État binaire pour chaque coupe en deux
return ok #Il est fondamentalement acceptable de sortir.(Selon le problème)
Courir
#La plage de recherche est 0~Jusqu'à N.
INF = N + 1
binSearch(-1, INF)
- Lors de l'exécution, commencez à partir d'un endroit ± 1 des deux extrémités (notez que peu importe la valeur extérieure entrée ici)
- Lors de l'appel, entrez dans l'ordre des arguments correspondant à ok et ng. (évidemment)
Exemple d'utilisation
1 Modèle simple pour trouver la valeur maximale qui satisfait la condition
INF = 10 ** 9 + 1
def main():
A, B, X = map(int, input().split())
# True - ng - ok - False
def is_ok(mid: int):
#Conditions de jugement
if mid < 0:
return True
elif mid >= INF:
return False
return A * mid + B * len(str(mid)) <= X
def binSearch(ok: int, ng: int):
#print(ok, ng)
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
#print(ok, ng)
return ok
print(binSearch(0, INF))
return
2 Modèle pour compter ceux qui remplissent les conditions
2-1 Problème simple
def main():
N = int(input())
L = [int(i) for i in input().split()]
L.sort()
# True ---- False
def is_ok_top(mid: int, a: int, b: int):
if mid < 0:
return True
elif mid >= N:
return False
return L[mid] < L[a] + L[b]
def binSearch_top(ok: int, ng: int, a: int, b: int):
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok_top(mid, a, b):
ok = mid
else:
ng = mid
return ok
count = 0
for a in range(0, len(L) - 2):
for b in range(a + 1, len(L) - 1):
count += binSearch_top(-1, INF, a, b) - b
print(count)
(TLE si ce n'est pas PyPy.)
2-2 Recherche dichotomisée à la fois au-dessus / au-dessous du seuil
- Point: Lorsqu'il y a trois valeurs de fluctuation, le nombre de motifs peut être supprimé en fixant le centre.
def solve(N: int, A: "List[int]", B: "List[int]", C: "List[int]"):
#Valeur maximum+Définir sur 1
INF = N + 1
A.sort()
B.sort()
C.sort()
# True - ok - ng - False
def is_ok(mid: int, b: int):
#Conditions de jugement
if mid < 0:
return True
elif mid >= N:
return False
return A[mid] < b
# False - ng - ok - True
def is_ok2(mid: int, b: int):
#Conditions de jugement
if mid < 0:
return False
elif mid >= N:
return True
return C[mid] > b
def binSearch(ok: int, ng: int, b: int):
#print(ok, ng)
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid, b):
ok = mid
else:
ng = mid
#print(ok, ng)
return ok
def binSearch2(ok: int, ng: int, b: int):
#print(ok, ng)
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok2(mid, b):
ok = mid
else:
ng = mid
#print(ok, ng)
return ok
sum = 0
for b in B:
a = binSearch(-1, INF, b) - 0 + 1
c = N - 1 - binSearch2(INF, -1, b) + 1
sum += a * c
#print(b, "->", a, c)
print(sum)
return
3 Lors de la recherche du Kth d'une liste triée. (Minimum X dans lequel le nombre de K-ième nombre X ou moins satisfait K ou plus)
Plus précisément, "Le problème de trouver le Kth lors de l'organisation en ligne. Cependant, lorsqu'il est trop grand pour énumérer tous les éléments."
ARC037 C -100 millions de calcul de masse
Ce problème peut être résolu en triant N ^ 2 nombres pour trouver le Kth, mais jusqu'à 9 * 10 ^ 8 TLE. Par conséquent, nous changeons la façon dont nous percevons le problème. Trouvez le Kth nombre X. = Il y a K nombres inférieurs à ce nombre X. Recherche dichotomisée à la condition que le nombre de produits X ou moins soit K ou plus.
Lors de la recherche du 5ème (K = 5) de 1,1,2,2,2,2,2,4,4.
2 en X = 1 (<5) → Non 7 à X = 2 (> = 5) → ok
Le cinquième se révèle être 2.
INF = 10 ** 18 + 1
def main():
N, K = map(int, input().split())
A = sorted([int(i) for i in input().split()])
B = sorted([int(i) for i in input().split()])
# False - ng - ok - True
def is_ok(mid: int):
#Conditions de jugement
if mid < 0:
return False
elif mid >= INF:
return True
count = 0
for a in A:
maxb = mid // a #La valeur maximale de b qui est inférieure ou égale à la valeur mid lorsque le produit est pris pour chaque a
count += bisect_right(B, maxb) #Si l'indice est obtenu à partir du B trié, tous les b avant qui sont b dont le produit avec a est n ou moins, et le nombre est obtenu.
return count >= K
def binSearch(ok: int, ng: int):
#print(ok, ng)
while abs(ok - ng) > 1:
mid = (ok + ng) // 2
if is_ok(mid):
ok = mid
else:
ng = mid
#print(ok, ng)
return ok
print(binSearch(INF, 0))
return
référence
https://www.forcia.com/blog/001434.html
Recommended Posts