[Pour les professionnels de la concurrence] Résumé de la file d'attente prioritaire (heapq)

Quand utiliser

  1. Lors de l'extraction rapide de l'élément maximum / minimum à chaque fois sous la condition que l'élément soit ajouté ultérieurement.
  2. Lorsqu'il y a deux conditions pour sélectionner un élément parmi les options. (Certains éléments ne peuvent être acquis tant que les conditions ne sont pas remplies. Parmi eux, la valeur maximale / minimale est acquise.)

Ce qui est bon

O (logN) pour push / pop O (1) pour obtenir le nombre d'éléments et la valeur minimale

Que faire

  1. ʻimport heapq`.
  2. Préparez une liste vide. ou heapify () une liste existante.
  3. Ajoutez un élément au tas avec heappush (heap, item).
  4. Récupérez l'élément minimum du tas avec heappop (heap).

Autres opérations

image

image.png

En pensant

Puisque le tas ne peut acquérir que la valeur minimale, si vous voulez prendre la valeur maximale, rendez tous les éléments négatifs à l'avance et insérez-le, et après l'acquisition, prenez la valeur absolue et renvoyez-la.

modèle

Pour 2 cas

def main():
    #Résumez les options pour chaque timing quand il devient disponible.

    #Changez les conditions.
    for n in range(N):
        #Mettre en file d'attente les choix qui seront disponibles(Je veux la valeur maximale lorsque je la retire, alors rendez-la négative.)

        #Si le tas n'est pas vide, choisissez la meilleure option et renvoyez un moins.

    return

Exemple d'utilisation

1 cas

ABC096 B - Maximum Sum

import heapq

def main():
    A, B, C = map(int, input().split())
    K = int(input())

    heap = [-A, -B, -C]
    heapq.heapify(heap)
    for _ in range(K):
        max = heapq.heappop(heap)
        heapq.heappush(heap, max * 2)
    
    sum = 0
    for i in heap:
        sum += i
    print(-sum)

2 cas

2nd Algorithm Practical Test F --Task Digestion

import heapq

def main():
    N = int(input())

    #Jour jour Gérez toutes les options qui peuvent être sélectionnées le jour.
    tasks = [[] for _ in range(N + 1)]
    for _ in range(N):
        a, b = map(int, input().split())
        tasks[a].append(b)

    heap = []
    points = 0

    for day in range(1, N + 1):
        #Mettre en file d'attente les choix qui seront disponibles(Je veux la valeur maximale lorsque je la retire, alors rendez-la négative.)
        for i in tasks[day]:
            heapq.heappush(heap, -i)
        #Si le tas n'est pas vide, choisissez la meilleure option et renvoyez un moins.
        if len(heap) > 0:
            points += abs(heapq.heappop(heap))
        print(points)
    return

Le sujet similaire ci-dessus

ABC137 D - Summer Vacation

Il y a deux conditions à sélectionner.

import heapq

def main():
    N, M = map(int, input().split())

    #Jour jour Gérez toutes les options qui peuvent être sélectionnées le jour.
    jobs = [[] for _ in range(M + 1)]
    for _ in range(N):
        a, b = map(int, input().split())
        if a > M:
            continue
        jobs[a].append(b)

    heap = []
    salary = 0

    #Cela remonte au jour M.
    for day in range(1, M + 1):
        #Mettre en file d'attente les choix qui seront disponibles(Je veux la valeur maximale lorsque je la retire, alors rendez-la négative.)
        for i in jobs[day]:
            heapq.heappush(heap, -i)
        #Si le tas n'est pas vide, choisissez la meilleure option et renvoyez un moins.
        if len(heap) > 0:
            salary += abs(heapq.heappop(heap))
    print(salary)
    return

référence

Recommended Posts

[Pour les professionnels de la concurrence] Résumé de la file d'attente prioritaire (heapq)
Résumé de la recherche Bisection pour les professionnels de la concurrence
[Pour les professionnels de la compétition] Résumé de la compression de la longueur de tirage
[Pour les professionnels de la concurrence] Résumé du doublement
[Pour les professionnels de la compétition] Résumé de l'arborescence de surface minimale
[Pour les professionnels de la concurrence] Union Find tree summary
Résumé de l'apprentissage RAPIDS