Il est facile d'oublier comment utiliser la fonction de dichotomie dans la programmation de compétitions, je la garderai donc en mémoire. Veuillez également noter que cet article ne couvre pas à quoi ressemble une dichotomie. De plus, veuillez noter que cet article est destiné à confirmer ** l'utilisation de base **.
En Python, le module bisect gère les fonctions liées à la dichotomie. Ce module prend en charge le travail avec ** liste triée (ascendante) ** dans l'ordre.
Dans la programmation de compétition, les deux fonctions suivantes sont principalement utilisées. Dans ce qui suit, l'élément à examiner est x, la ** liste triée (ascendante) ** à examiner est a, le premier argument est a et le second argument est x. La plage à examiner dans a peut être spécifiée dans les 3e et 4e arguments, mais elle n'est pas traitée ici. Voir module bisect.
①bisect_left Renvoie l'index du point d'insertion à a à l'extrême gauche de x (dans l'ordre). $ \ leftrightarrow Renvoie l'index du plus petit élément au-dessus de $ x. $ \ leftrightarrow $ L'élément à gauche est le plus grand élément (index) plus petit que x.
②bisect_right Renvoie l'index du point d'insertion à a à l'extrême droite de x (dans l'ordre). $ \ leftrightarrow Renvoie l'index du plus petit élément qui est plus grand que $ x. $ \ leftrightarrow $ L'élément à gauche est le plus grand élément (index) sous x.
En C ++, la bibliothèque d'algorithmes gère les fonctions liées à la dichotomie. Dans cette bibliothèque, ** toute structure de données qui a un itérateur qui répond aux exigences de l'algorithme ** fonctionnera.
Dans la programmation de compétition, les deux fonctions suivantes sont principalement utilisées. De plus, comme précédemment, laissez x être l'élément que vous voulez vérifier, et laissez a le ** tableau trié (croissant) ** à vérifier. À ce stade, spécifiez la plage à examiner avec le premier argument comme a.begin () et le deuxième argument comme a.end (), et spécifiez l'élément x à examiner dans le troisième argument.
①lower_bound Synonyme de bisect_left de Python, mais renvoie le plus petit élément ** itérateur ** avec des éléments supérieurs ou égaux à x. De plus, si vous voulez obtenir le ** index ** minimum, vous pouvez l'obtenir avec (valeur de retour) -a.begin ().
②upper_bound Synonyme de bisect_right de Python, mais renvoie le ** itérateur ** du plus petit élément plus grand que x. De plus, si vous voulez obtenir le ** index ** minimum, vous pouvez l'obtenir avec (valeur de retour) -a.begin ().
✳︎ Ordre croissant La liste triée est obligatoire, mais elle peut être triée même si elle n'est pas par ordre croissant en surchargeant l'opérateur. ✳︎ Si vous voulez en savoir plus sur C ++ lower_bound et upper_bound, veuillez consulter cet article. ✳︎ Si vous avez d'autres choses importantes, faites-le nous savoir dans les commentaires!
Recommended Posts