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()
Unlike STL in C ++, heappop () in python comes out from the smallest element, so it corresponds by inverting the sign.
# -*- 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
Heapq solution. Since it is brought from the smallest element, python's heapq is as it is. The amount of calculation is O (L, n log n).
# -*- 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
No, it's funny. By duplicating the elements, you can reduce the problem of grouping, so Union-Find can process it at high speed.
Priority queue, binary search tree, Union-Find tree introduction and exercises.
For the time being, I wrote it using the heapq and unionfind packages.
Before going to Sec2-5, I'll try to implement each one myself.
Recommended Posts