Ant book in python: Sec. 2-4, data structures

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.

page75: Fence Repair (PKU 3253) Again



# -*- 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).

page85: Food Chain (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

No, it's funny. By duplicating the elements, you can reduce the problem of grouping, so Union-Find can process it at high speed.

After finishing Sec2-4

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

Ant book in python: Sec. 2-4, data structures
Ant book in python: Sec. 2-5 Graph
Ant book in python: Sec.2-5 Dijkstra's algorithm
Ant book in python: Sec. 2-5 Graph (preparation)
Ant book in python: Sec. 2-3, Dynamic Programming (DP)
Ant book in python: page 42 coin problem
Ant book in python: Priority queue self-implementation
Ant book in python: page 43 Interval scheduling
Ant book in python: page 49 Fence Repair
Ant book in python: page 47 Saruman's Army (POJ 3069)
Handle Ambient data in Python
Display UTM-30LX data in Python
Ant book in python: page 45 Dictionary order minimum problem (POJ3617)
Get Leap Motion data in Python.
Read Protocol Buffers data in Python3
Get data from Quandl in Python
Handle NetCDF format data in Python
Python data structures learned with chemoinformatics
Hashing data in R and Python
Picture book data structure algorithm Python
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part1-
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part2-
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part4-
Solving AOJ's Algorithm and Introduction to Data Structures in Python -Part3-
[Python] Chapter 04-06 Various data structures (creating dictionaries)
Get additional data in LDAP with python
Spiral book in Python! Python with a spiral book! (Chapter 14 ~)
Data input / output in Python (CSV, JSON)
Try working with binary data in Python
[Python] Chapter 04-03 Various data structures (multidimensional list)
[Python] Chapter 04-04 Various data structures (see list)
Get Google Fit API data in Python
Python: Preprocessing in machine learning: Data acquisition
Get Youtube data in Python using Youtube Data API
Ant book with python (chapter3 intermediate edition ~)
[Python] Chapter 04-02 Various data structures (list manipulation)
Easily graph data in shell and Python
[Python] Chapter 04-07 Various data structures (dictionary manipulation)
Python: Preprocessing in machine learning: Data conversion
Working with 3D data structures in pandas
[Python] [Supplement] Chapter 04-09 Various data structures (set theory and operations in sets)
Get time series data from k-db.com in Python
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Meta-analysis in Python
Python variables and data types learned in chemoinformatics
Unittest in python
Data analysis python
Receive and display HTML form data in Python
[Python] Swapping rows and columns in Numpy data
Epoch in Python
Discord in Python
Read table data in PDF file with Python
Real-time visualization of thermography AMG8833 data in Python
Sudoku in Python
DCI in Python