Quand utiliser

Lors de l'extraction rapide de l'élément maximum / minimum à chaque fois sous la condition que l'élément soit ajouté ultérieurement.
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

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

Autres opérations

Si vous voulez faire 2 et 3 en même temps, vous pouvez pop après avoir poussé vers le tas avec heappushpop (tas, item) (c'est plus efficace)
Pour accéder au plus petit élément sans popping, définissez l'index sur 0 et accédez avec l'opérateur bracket.

image

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.

Obtenez des récompenses par M jours → Si vous revenez de M jours, vous pouvez sélectionner plus de tâches.
Obtenez la valeur maximale parmi eux
2 Lors de la sélection à partir des conditions, il est préférable de commencer par les conditions les plus strictes.

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

https://docs.python.org/ja/3/library/heapq.html

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