Livre Ali en python: Sec.2-4, structure de données

page 73: Expedition (POJ 2421)

# -*- coding: utf-8 -*-

from heapq import *

N = int(raw_input())
L = int(raw_input())
P = int(raw_input())
A = map(int,raw_input().split())
B = map(int,raw_input().split())

h = []

fuel = P
position = 0
ans = 0

A.append(L)
B.append(0)
N += 1

def solve():

    h = []

    fuel = P
    position = 0
    ans = 0


    for i in range(N):
        dl = A[i]-position

        while fuel - dl <0:
            if len(h) == 0:
                return -1
            fuel += -heappop(h)
            ans += 1
        fuel -=dl
        position = A[i]
        heappush(h,-B[i])

    return ans

print solve()

Contrairement à C ++ STL, python heappop () sort du plus petit élément, il correspond donc en inversant le signe.

page75: Réparation de clôture (PKU 3253) à nouveau

# -*- coding: utf-8 -*-

from heapq import *

N = int(raw_input())
L = map(int,raw_input().split())

h = []

cost = 0

for i in L:
    heappush(h,i)

while len(h)>1:
    l1 = heappop(h)
    l2 = heappop(h)
    cost += l1 + l2
    heappush(h,l1+l2)

print cost

La solution par heapq. Puisqu'il est importé du plus petit élément, le tas de python est tel qu'il est. Le montant du calcul est O (L, n log n).

page85: Chaîne alimentaire (POJ 1182)

# -*- coding: utf-8 -*-

from heapq import *
from unionfind import *

N = int(raw_input())
K = int(raw_input())
information = []
while 1:
    a = raw_input()
    if a == "":
        break
    information.append(map(int,a.split()))

u = unionfind(3 * N) 

ans = 0
for i in information:
    infclass = i[0]
    x = i[1]
    y = i[2]

    if x < 0 or x >=N or y <0 or y >=N or infclass <1 or infclass >2:
        ans +=1
        continue
    if infclass == 1:
        if u.issame(x, y+N) or u.issame(x, y+2*N):
            ans +=1
            continue
        else:
            u.unite(x, y)
            u.unite(x+N, y+N)
            u.unite(x+2*N, y+2*N)

    if infclass ==2:
        if u.issame(x, y) or u.issame(x, y+2*N):
            ans +=1
            continue
        else:
            u.unite(x, y+N)
            u.unite(x+N, y+2*N)
            u.unite(x+2*N, y)

print ans

Non, c'est drôle. En dupliquant les éléments, vous pouvez réduire le problème de regroupement, afin que Union-Find puisse les traiter à grande vitesse.

Après avoir terminé Sec2-4

Introduction et exercices pour les files d'attente prioritaires, les arbres de dichotomie, les arbres Union-Find.

Pour le moment, je l'ai écrit en utilisant les packages de recherche heapq et union.

Avant de passer à Sec2-5, je vais essayer de mettre en œuvre chacun d'eux moi-même.