L'explication utilisant multiset a été écrite dans le problème E d'AtCoder Beginner Contest, mais je pense qu'il existe des langages tels que python qui n'ont pas de mutiset, je voudrais donc introduire un algorithme alternatif utilisant Priority Queue (heapq). Je n'expliquerai pas le problème lui-même, alors veuillez lire l'explication officielle ici.
ABC170 E - Smart Infants https://atcoder.jp/contests/abc170/tasks/abc170_e
multiset En interne [Arbre de dichotomie](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C % A8) est utilisé. Cela maintient les données triées à tout moment au lieu de prendre O (logN) chaque fois qu'une donnée est insérée. Par conséquent, il est possible de supprimer et de rechercher avec O (logN). En implémentant vous-même l'arbre de dichotomie, vous pouvez l'utiliser dans des langues qui ne sont pas fournies en standard, mais vous devez concevoir pour maintenir l'équilibre. (Exemple d'ingéniosité: [Formation de maître bois] 7-1. Qu'est-ce que le bois Splay? Explication [Compétition professionnelle Katsuppa])
Priority Queue En interne dans GCC [Dichotomy](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E3%83%92%E3%83%BC%E3%83 % 97) est utilisé. La même structure de données est utilisée en interne dans heapq de python. L'insertion de données prend O (logN) à chaque fois, comme l'arbre de dichotomie. Puisqu'il s'agit d'un arbre de tas, l'intérieur n'est ** pas trié, et vous ne pouvez pas rechercher ou supprimer autre chose que la valeur maximale (minimale) à grande vitesse **, mais vous ne pouvez pas toujours obtenir la valeur maximale (minimale) avec le montant de calcul O (1). Je peux le faire. L'avantage par rapport à l'arbre de dichotomie est que la quantité de calcul est stable car l'équilibre est toujours maintenu sans aucune ingéniosité particulière.
Dans ce problème
Ce serait bien si cela pouvait toujours être fait à grande vitesse.
Comme mentionné dans le commentaire officiel, chaque processus peut être exécuté à grande vitesse en utilisant le multiset, mais comme le 4ème processus ne peut pas être exécuté à grande vitesse avec Priority Queue, il est nécessaire de changer la façon de penser.
En résolvant ce problème, notons que la quatrième condition n'est ** pas nécessairement un processus qui doit être exécuté à moins qu'il n'interfère avec les première et deuxième conditions **. En d'autres termes, même si elle n'est pas réellement supprimée des données, peu importe si la valeur maximale du taux fixé et la valeur minimale du taux maximal fixé dans chaque jardin d'enfants ne sont pas affectées.
Puisque l'implémentation ne change pas dans les première et seconde conditions (le maximum et le minimum sont retournés), la première condition (obtenir la valeur maximum de l'ensemble) sera expliquée à titre d'exemple.
Pensez maintenant à avoir deux files d'attente prioritaires.
Et ** insérez un élément en 1 lorsque vous entrez dans le parc et en 2 lorsque vous changez de parc. Si les maximums de 1 et 2 sont identiques, supprimez-les des deux. ** ** Cela garantit que la valeur maximale pour ce jardin d'enfants est toujours la même que la valeur maximale pour 1.
Je vais mettre du code ici, mais cela ne fonctionne pas même si je le copie en fonction de l'environnement car std et include sont cassés.
code.cpp
priority_queue<int> in;
priority_queue<int> out;
//Traitement lors de l'entrée dans le parc
void infant_in(int i){
in.push(i);
}
//Traitement lors du changement de jardin
void infant_out(int i){
out.push(i);
while(!out.empty() && in.top() == out.top()){
in.pop();
out.pop();
}
}
//Obtenez le maximum
int get_max(){
return in.top();
}
Regardons un exemple concret. Considérez que les enfants avec un taux de 3,5,8 entrent à la maternelle, puis les enfants avec un taux de 5,8 se déplacent dans cet ordre.
>Trois enfants de la maternelle entrent
Maternelle réelle= {3,5,8}
1 = [3,5,8] 2 = [] #Bien sûr, la valeur maximale à ce stade est de 8
>Les enfants avec un tarif de 5 sont transférés
Maternelle réelle= {3,8}
1 = [3,5,8] 2 = [5] #La valeur maximale est 8
>Les enfants avec un tarif de 8 sont transférés
Maternelle réelle= {3}
1 = [3,5,8] 2 = [5,8]
1 = [3,5] 2 = [5]
1 = [3] 2 = [] #La valeur maximale est 3
Avec ce genre de sentiment, vous pouvez voir qu'il n'y a aucun problème à obtenir la valeur maximale.
C'est un montant de calcul dont il faut s'inquiéter, mais comme le nombre de fois pour supprimer la valeur d'entrée et de sortie qui semble être un goulot d'étranglement dans ce problème est Q fois au maximum, il peut être ignoré et le montant du calcul est O (NlogN) requis lors de l'insertion de la valeur. Devenir. C'est assez rapide.
Recommended Posts