CẤU TRÚC HEAP VÀ ỨNG DỤNG
I. LỜI NÓI ĐẦU
Có thể nói Heap là 1 cấu trúc hữu dụng vào bậc nhất trong giải toán. Trong
khoa học máy tính, đống (tiếng Anh: heap) là một cấu trúc dữ liệu dựa trên cây thỏa
mãn tính chất đống: nếu B là nút con của A thì khóa(A)≥khóa(B) (HEAP MAX) .
Một hệ quả của tính chất này là khóa lớn nhất luôn nằm ở nút gốc. Do đó một đống
như vậy thường được gọi là đống-max. Nếu mọi phép so sánh bị đảo ngược khiến
cho khóa nhỏ nhất luôn nằm ở nút gốc thì đống đó gọi là đống-min. Thông thường
mỗi nút có không quá hai nút con. Mục đích của heap trong các bài các bài toán tin là
ta có thể truy xuất phần tử lớn nhất hay nhỏ nhất có trong một mảng lưu trữ hiện tại.
Do đó có 2 loại là heap_max và heap_min. Đống là một cách thực hiện kiểu dữ liệu
trừu tượng mang tên hàng đợi ưu tiên. Đống có vai trò quan trọng trong nhiều thuật
toán
Một số ứng dụng của Heap:
+ Heapsort: Một trong những phương pháp sắp xếp tại chỗ tốt nhất
+ Thuật toán lựa chọn: có thể sử dụng đống để tìm phần tử lớn nhất, nhỏ nhất, trung
vị, phần tử lớn thứ k, trong thời gian tuyến tính.
+ Thuật toán cho đồ thị: nhiều thuật toán cho đồ thị sử dụng cấu trúc dữ liệu đống
chẳng hạn như thuật toán Dijkstra, hay thuật toán Prim.
Các thao tác thường gặp trên đống là:
+ Tìm-max (tìm-min): tìm khóa lớn nhất trong đống-max (tìm khóa nhỏ nhất trong
đống-min).
+ Xóa-max (xóa-min): xóa nút gốc của đống-max (đống-min)
+ tăng-khóa (giảm-khóa): thay đổi giá trị một khóa trong đống-max (đống-min)
+ chèn: chèn thêm một khóa mới vào đống
+ hợp: hợp hai đống lại thành một đống mới chứa tất cả các khóa của cả hai
II. CẤU TRÚC HEAP
1
Heap được biểu diễn bằng cây nhị phân, nút k trên cây sẽ có hai nút con là 2*k
và 2*k+1, có cha là k div 2. Heap[k] tùy theo loại heap mà nó lớn hơn con nó hay cha
nó. Mỗi khi ta thay đổi một phần tử bất kì trong heap thì ta sẽ cập nhật lại heap trong
khoảng thời gian log n. Có hai thao tác đối với heap là upheap và downheap.
Heap sẽ cần biến nh để quản lí số lượng phần tử của heap.
Ví dụ với HEAP MAX
Các thao tác thường dùng trong xử lý HEAP:
- Up_heap: nếu 1 nút lớn hơn cha của nó thì di chuyển nó lên trên
- Down_heap: nếu 1 phần tử nhỏ hơn 1 con của nó thì di chuyển nó xuống dưới
- Push: đưa 1 phần tử vào HEAP bằng cách thêm 1 nút vào cây và up_heap nút đó
- Del: loại 1 phần tử khỏi HEAP bằng cách chuyển nó xuống cuối heap và loại bỏ,
sau đó chỉnh sửa lại heap sao cho thoả mãn các điều kiện của HEAP.
Trong code x là vị trí, a là giá trị, nh là số phần tử, pa là cha của x, c là con của
x.
void upheap(int x)
{
if (x == 1) return;
int pa = x/2;
if(heap[x] > heap[pa]){
swap(heap[x],heap[pa]);
upheap(pa);
}
}
void push(int a)
{
nh++;
heap[nh] = a;
upheap(nh);
}
//
//
//
//
//
x là gốc thì làm gì có cha
cha của x
x hơn cha nó nên đi lên
đổi chỗ
up cha nó
// đẩy giá trị a vào
// tăng số lượng
// cho a vô
// đẩy a lên
void downheap(int x)
{
int c = x*2;
// con của x
if(c > nh)return;
// không có con thì thoát
if(c < nh and heap[c+1] > heap[c]) c++;
// nếu nó còn con 2 thì chọn con lớn để khi kéo nó
// lên đảm bảo thằng này lúc làm cha sẽ lớn hơn
2
// thằng con không được làm cha
if(heap[x] < heap[c]){
// nếu kéo được thì kéo
swap(heap[x],heap[c]); // đổi chỗ
downheap(c);
// down nó
}
}
void del(int x)
{
heap[x] = heap[nh];
nh--;
downheap(x);
upheap(x);
}
// kéo thằng cuối lên x
// giảm số phần tử
// cập nhật lại
Heap được sử dụng trong thuật toán Dijkstra, Kruskal, Heap Sort nhằm giảm
độ phức tạp thuật toán. Heap còn có thể sử dụng trong các bài toán dãy số, QHĐ, đồ
thị... Với những ví dụ sau ta sẽ thấy phần nào sự đa dạng và linh hoạt trong sử dụng
Heap.
III. BÀI TẬP ỨNG DỤNG CẤU TRÚC HEAP
1. KMIN http://vn.spoj.com/problems/KMIN
Ý tưởng: Ban đầu sort không giảm hai dãy a,b. Cho a[1] + b[i] với i = 1 -> n vào 1
heap_min. Duyệt k lần , mỗi lần lấy gốc ra rồi cho a[i+1] + b[j] vào với i, j là vị trí
của nút vừa lấy ra, nếu i = n thì thôi.
1. const fi='';
2.
fo='';
3. type mang=array[1..50000] of longint;
4.
sum=record i, j: longint; end;
5. var
f: text;
6.
a, b: mang;
7.
m, n, k, top: longint;
8.
heap: array[1..50000] of sum;
9. {------------------------------------------------------------------}
10.
procedure enter;
11.
var
i: longint;
12.
begin
13.
assign(f, fi);
14.
reset(F);
15.
readln(f, m, n, k);
16.
for i:=1 to m do readln(f, a[i]);
17.
for i:=1 to n do readln(f, b[i]);
18.
close(F);
19.
end;
3
20.
{------------------------------------------------------------------}
21.
22.
23.
24.
25.
function cmp(x, y: sum): boolean;
begin
exit(a[x.i]+b[x.j]>=a[y.i]+b[y.j]);
end;
{-------------------------------------------------------------------}
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
procedure swap(i, j: longint);
var
tg: sum;
begin
tg:=heap[i];
heap[i]:=heap[j];
heap[j]:=tg;
end;
{--------------------------------------------------}
procedure upheap(i: longint);
begin
if (i=1) or cmp(heap[i], heap[i div 2]) then exit;
swap(i, i div 2);
upheap(i div 2);
end;
{------------------------------------------------------------------}
procedure downheap(i: longint);
var
j: longint;
begin
j:=i*2;
if j>top then exit;
if (j=H then exit;
key:=x[random(H-L+1)+L];
i:=L;
j:=H;
repeat
while x[i]key do dec(j);
4
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
---}
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
-}
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
}
122.
123.
124.
125.
126.
if i<=j then
begin
if ij;
sort(x, L, j);
sort(x, i, H);
end;
{------------------------------------------------------------------procedure solve;
var
i: longint;
begin
sort(a, 1, m);
sort(b, 1, n);
top:=n;
for i:=1 to n do
begin
heap[i].i:=1;
heap[i].j:=i;
end;
end;
{------------------------------------------------------------------procedure print;
var
i: longint;
begin
assign(f, fo);
rewrite(f);
for i:=1 to k do
begin
writeln(f, a[heap[1].i]+b[heap[1].j]);
if heap[1].i=a[i div 2]) then exit;
20.
swap(i, i div 2);
21.
upheap(i div 2);
22.
end;
23.
{------------------------------------------------------------------}
24.
procedure downheap(i: longint);
25.
var
j: longint;
26.
begin
27.
j:=i*2;
28.
if j>top then exit;
29.
if (ja[j+1]) then inc(j);
30.
if a[i]>a[j] then swap(i, j);
31.
downheap(j);
32.
end;
33.
{----------------------------------------------------------------------}
34.
procedure push(x: longint);
35.
begin
36.
inc(top);
37.
a[top]:=x;
38.
upheap(top);
39.
end;
40.
{---------------------------------------------------------}
41.
procedure pop;
42.
begin
43.
a[1]:=a[top];
44.
dec(top);
45.
downheap(1);
46.
end;
47.
{------------------------------------------------------}
48.
procedure enter;
49.
var
i: longint;
50.
c: longint;
51.
begin
52.
top:=0;
6
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
readln(f, n);
for i:=1 to n do
begin
read(f, c);
push(c);
end;
end;
{-----------------------------------------------------------}
procedure solve;
var
i: longint;
x, y: longint;
begin
kq:=0;
for i:=1 to n-1 do
begin
x:=a[1];
pop;
y:=a[1];
pop;
push(x+y);
kq:=kq+x+y;
end;
writeln(kq);
end;
{------------------------------------------------------------------}
BEGIN
assign(f, fi);
reset(f);
readln(f, t);
for k:=1 to t do
begin
enter;
solve;
end;
close(F);
END.
3. QBHEAP http://vn.spoj.com/problems/QBHEAP
Ý tưởng: Mỗi lần “+”V thì đẩy phần tử V vào heap bằng thủ tục Push. Thao tác “” : Nếu danh sách đang không rỗng thì thao tác này loại bỏ tất cả các phần tử lớn
nhất của danh sách bằng thủ tục Del đến khi nào đầu heap nhỏ hơn Max hiện tại.
1. const fi='';
2.
fo='';
3. var
f: text;
4.
a: array[1..15000] of longint;
5.
top, n: integer;
6. {--------------------------------------------------------}
7. procedure swap(i, j: integer);
8. var
tg: longint;
9. begin
10.
tg:=a[i];
11.
a[i]:=a[j];
12.
a[j]:=tg;
7
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
end;
{-----------------------------------------------------}
procedure upheap(i: integer);
begin
if (i=1) or (a[i]<=a[i div 2]) then exit;
swap(i, i div 2);
upheap(i div 2);
end;
{------------------------------------------------------------------}
procedure downheap(i: integer);
var
j: integer;
begin
j:=i*2;
if j>top then exit;
if (j0) and (a[1]=key) do pop;
readln(f);
end;
8
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
end;
n:=top;
for i:=n downto 2 do
begin
swap(i, 1);
dec(top);
downheap(1);
end;
close(F);
end;
{---------------------------------------------------------------}
procedure print;
var
i, count: integer;
begin
assign(f, fo);
rewrite(F);
if n=0 then
begin
writeln(f, 0);
close(F);
exit;
end;
count:=1;
for i:=2 to n do if a[i]<>a[i-1] then inc(count);
writeln(f, count);
write(f, a[n], ' ');
for i:=n-1 downto 1 do
if a[i]<>a[i+1] then write(f, a[i], ' ');
close(F);
end;
{--------------------------------------------------------}
BEGIN
enter;
print;
END.
4.MEDIAN http://vn.spoj.com/problems/MEDIAN
Ý tưởng: Dùng 2 heap, 1 heap (HA) lưu các phần tử từ thứ 1 tới N div 2 và heap còn
lại (HB) lưu các phần tử từ N div 2 +1 tới N sau khi đã sort lại tập thành tăng dần.
HA là Heap-max còn HB là Heap-min. Như vậy phần tử trung vị luôn là gốc HB (N
lẻ) hoặc gốc của cả HA và HB (n chẵn). Thao tác MEDIAN do đó chỉ có độ phức tạp
O(1). Còn thao tác PUSH sẽ được làm trong O(logN).
- Nếu gtr đưa vào nhỏ hơn hoặc bằng HA[1] đưa vào HA ngược lại đưa vào HB. Số
phần tử N của tập tăng lên 1.
- Nếu HA có lớn hơn (/nhỏ hơn N) div 2 phần tử thì POP 1 phần tử từ HA (/HB) đưa
vào heap còn lại. Sau quá trình trên thì HA và HB vẫn đảm bảo đúng theo định nghĩa
ban đầu. Bài toán được giải quyết với độ phức tạp O(MlogM).
9
1. //uses sysutils;
2. const fi='';
3.
fo='';
4. type pt=record gt: longint; vt: longint; end;
5.
heap=array[1..2510] of pt;
6. var
{t1, t2: tdatetime;}
7.
f1, f2: text;
8.
pos: array[1..250000] of longint;
9.
a: array[1..250000] of pt;
10.
heapa, heapb: heap;
11.
n, k, seed, add, topa, topb: longint;
12.
mul, s: int64;
13.
t, it: byte;
14.
{------------------------------------------------}
15.
procedure swapa(i, j: longint);
16.
var
tg: pt;
17.
begin
18.
tg:=heapa[i];
19.
heapa[i]:=heapa[j];
20.
heapa[j]:=tg;
21.
pos[heapa[i].vt]:=i;
22.
pos[heapa[j].vt]:=j;
23.
end;
24.
{--------------------------------------------------}
25.
procedure upheapa(i: longint);
26.
begin
27.
if (i=1) or (heapa[i].gt<=heapa[i div 2].gt) then exit;
28.
swapa(i, i div 2);
29.
upheapa(i div 2);
30.
end;
31.
{------------------------------------------------------------------}
32.
procedure downheapa(i: longint);
33.
var
j: longint;
34.
begin
35.
j:=i*2;
36.
if j>topa then exit;
37.
if (j=heapa[j].gt then exit;
39.
swapa(i, j);
40.
downheapa(j);
41.
end;
42.
{----------------------------------------------------------------------}
43.
procedure pusha(i: longint);
44.
begin
45.
inc(topa);
46.
heapa[topa]:=a[i];
47.
pos[a[i].vt]:=topa;
48.
upheapa(topa);
49.
end;
50.
{--------------------------------------------------}
51.
procedure popa(i: longint);
52.
begin
53.
heapa[i]:=heapa[topa];
54.
pos[heapa[i].vt]:=i;
55.
dec(topa);
56.
upheapa(i);
57.
downheapa(i);
58.
end;
10
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
{--------------------------------------}
procedure swapb(i, j: longint);
var
tg: pt;
begin
tg:=heapb[i];
heapb[i]:=heapb[j];
heapb[j]:=tg;
pos[heapb[i].vt]:=i+(k+1) div 2;
pos[heapb[j].vt]:=j+(k+1) div 2;
end;
{--------------------------------------------------}
procedure upheapb(i: longint);
begin
if (i=1) or (heapb[i].gt>=heapb[i div 2].gt) then exit;
swapb(i, i div 2);
upheapb(i div 2);
end;
{------------------------------------------------------------------}
procedure downheapb(i: longint);
var
j: longint;
begin
j:=i*2;
if j>topb then exit;
if (jheapb[j+1].gt) then inc(j);
if heapb[i].gt<=heapb[j].gt then exit;
swapb(i, j);
downheapb(j);
end;
{-------------------------------------------------------------------
----}
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
procedure pushb(i: longint);
begin
inc(topb);
heapb[topb]:=a[i];
pos[a[i].vt]:=topb+(k+1) div 2;
upheapb(topb);
end;
{--------------------------------------------------}
procedure popb(i: longint);
begin
heapb[i]:=heapb[topb];
pos[heapb[i].vt]:=i+(k+1) div 2;
dec(topb);
upheapb(i);
downheapb(i);
end;
{--------------------------------------------------------------}
procedure sort(L, H: integer);
var
i, j: integer;
key: longint;
tg: pt;
begin
if L>=H then exit;
key:=a[random(H-L+1)+L].gt;
i:=L;
j:=H;
repeat
while a[i].gtkey do dec(j);
11
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
if i<=j then
begin
tg:=a[i];
a[i]:=a[j];
a[j]:=tg;
inc(i);
dec(j);
end;
until i>j;
sort(L, j);
sort(i, h);
end;
{-------------------------------------------------------_-----}
procedure solve;
var
i: longint;
begin
readln(f1, seed, mul, add, n, k);
fillchar(a, sizeOf(a), 0);
topa:=(k+1) div 2;
topb:=k-(k+1) div 2;
a[1].gt:=seed;
a[1].vt:=1;
s:=a[1].gt;
for i:=2 to n do
begin
a[i].gt:=(a[i-1].gt*mul+add) mod 65536;
a[i].vt:=i;
s:=s+a[i].gt;
end;
if k=1 then
begin
writeln(f2, 'Case #', it, ': ', s);
exit;
end;
{for i:=1 to n do writeln(f2, i, '.
', a[i].gt);}
sort(1, k);
for i:=1 to (k+1) div 2 do
begin
heapa[i]:=a[(k+1) div 2+1-i];
pos[a[(k+1) div 2+1-i].vt]:=i;
end;
for i:=(k+1) div 2+1 to k do
begin
heapb[i-(k+1) div 2]:=a[i];
pos[a[i].vt]:=i;
end;
s:=0;
i:=1;
while i<=n-k+1 do
begin
s:=s+heapa[1].gt;
if pos[i]<=(k+1) div 2 then popa(pos[i])
else popb(pos[i]-(k+1) div 2);
if i=n-k+1 then break;
{a[i+k].vt:=i+k;
a[i+k].gt:=(a[i+k-1].gt*mul+add) mod 65536; }
if a[i+k].gt<=heapa[1].gt then pusha(i+k)
else pushb(i+k);
if topb>k-(k+1) div 2 then
12
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
begin
inc(topa);
heapa[topa]:=heapb[1];
pos[heapa[topa].vt]:=topa;
upheapa(topa);
popb(1);
end;
if topa>(k+1) div 2 then
begin
inc(topb);
heapb[topb]:=heapa[1];
pos[heapb[topb].vt]:=topb+(k+1) div 2;
upheapb(topb);
popa(1);
end;
inc(i);
end;
writeln(f2, 'Case #', it, ': ', s);
end;
{--------------------------------------------------}
BEGIN
assign(f1, fi);
reset(f1);
assign(f2, fo);
rewrite(F2);
{t1:=now; }
readln(f1, t);
for it:=1 to t do solve;
{t2:=now;
writeln((t2-t1)*3600*24:0:6);}
close(f1);
close(f2);
END.
5. BALLGAME http://vn.spoj.com/problems/BALLGAME
Ý tưởng: Đầu tiên ta sắp xếp lại thứ tự thời gian của các cuộc ném bóng. Bài này
ta dùng 3 heap với các ý nghĩa như sau: 1 heap min, 1 heap max lưu chỉ sô các lỗ
còn trống, 1 heap quản lí các ô đang có bóng xoáy ở trên, heap này là 1 heap min
với giá trị khóa là thời gian quả bong rơi xống lỗ. Đầu tiên 2 heap min và max đầy
(tât cả các ô còn trông). Cho 1 vòng for qua các thứ tự ném, đến 1 lượt ta phải làm
2 việc sau:
1: Loại bỏ từ Heap quản lí các ô có bóng những ô nào có thời gian rơi xuống lỗ ≤
thời gian ném bóng của lượt này, sau đó thêm vào heap min và heap max những ô
tìm được những ô này lần lượt lấy ra từ heap quản lý.
13
2: Thực hiện ném: nếu từ bên trái thì dựa vào heap min để tìm ô trống có chỉ số
nhỏ nhất, nếu ném bên phải thì ngược lại. Khi tìm được thì loại bỏ khỏi 2 heap này
phần tử tìm được, thêm phần tử vào heap quản lý gồm 2 thông tin chỉ số của lỗ và
thời gian rơi xuống lỗ. Cứ làm như thế cho đến khi hết bóng hoặc không còn lỗ
nào trống thì dừng lại. Chú ý cần phải lưu số hiệu các ô trong hai heap để tiện cho
việc loại bỏ.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
{$R-, Q-}
{$MODE OBJFPC}
PROGRAM
MALLGAME;
CONST
mmax
=
100000;
TYPE
lannem
=
record
time, xoay: longint;
ten
: char;
end;
VAR
a
:
hmi, hma:
hql
:
vti, vta:
vthql
:
d
:
bb
:
hoa
:
alice
:
n, m, tg:
tc
:
nhi, nha:
nhql
:
slA, slB:
f, g
:
procedure
openf;
begin
assign(f, '');
assign(g, '');
end;
array [1..
array [1..
array [1..
array [1..
array [1..
array [1..
array [1..
boolean;
boolean;
longint;
longint;
longint;
longint;
longint;
text;
mmax]
mmax]
mmax]
mmax]
mmax]
mmax]
mmax]
of
of
of
of
of
of
of
lannem;
longint;
longint;
longint;
longint;
longint;
longint;
inline;
reset(f);
rewrite(g);
procedure
closef;
inline;
begin
close(f);
close(g);
end;
14
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
procedure
readf;
inline;
var
i: longint;
begin
readln(f, n, m);
for i:= 1 to m do
readln(f, a[i]. ten, a[i]. time, a[i]. xoay);
end;
procedure
swap(var a, b: lannem);
var
c: lannem;
begin
c:= a; a:= b;
b:= c;
end;
procedure
sort(d, c: longint);
var
i, j: longint;
t
: lannem;
begin
if d>= c then
exit;
inline;
inline;
i:= d; j:= c;
t:= a[random(c- d+ 1)+ d];
repeat
while a[i]. time< t. time do
inc(i);
while a[j]. time> t. time do
dec(j);
if i<= j then
begin
if i< j then
swap(a[i], a[j]);
inc(i);
dec(j);
end;
until i> j;
sort(d, j);
sort(i, c);
end;
procedure
doicho(var a, b: longint);
var
c: longint;
begin
c:= a;
a:= b;
b:= c;
end;
procedure
upheaphmi(i: longint);
var
j: longint;
begin
inline;
inline;
15
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
while i shl 1<= nhi do
begin
j:= i shl 1;
if (j< nhi)and (hmi[j]> hmi[j+ 1]) then
inc(j);
if hmi[j]>= hmi[i] then
exit;
doicho(hmi[i], hmi[j]);
vti[hmi[i]]:= i;
vti[hmi[j]]:= j;
i:= j;
end;
end;
procedure
downheapmi(i: longint);
var
j: longint;
begin
while i> 1 do
begin
j:= i shr 1;
if hmi[i]>= hmi[j] then
exit;
doicho(hmi[i], hmi[j]);
vti[hmi[i]]:= i;
vti[hmi[j]]:= j;
i:= j;
end;
end;
inline;
procedure
upheaphma(i: longint);
inline;
var
j: longint;
begin
while i shl 1<= nha do
begin
j:= i shl 1;
if (j< nha)and (hma[j]<= hma[j+ 1]) then
inc(j);
if hma[j]<= hma[i] then
exit;
doicho(hma[i], hma[j]);
vta[hma[i]]:= i;
vta[hma[j]]:= j;
i:= j;
end;
end;
procedure
downheapma(i: longint);
var
j: longint;
begin
while i> 1 do
begin
j:= i shr 1;
if hma[i]<= hma[j] then
exit;
inline;
16
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
doicho(hma[i], hma[j]);
vta[hma[i]]:= i;
vta[hma[j]]:= j;
i:= j;
end;
end;
procedure
upheaphql(i: longint); inline;
var
j: longint;
begin
while i shl 1<= nhql do
begin
j:= i shl 1;
if (j< nhql)and (d[hql[j]]>= d[hql[j+ 1]]) then
inc(j);
if d[hql[j]]>= d[hql[i]] then
exit;
doicho(hql[i], hql[j]);
vthql[hql[i]]:= i;
vthql[hql[j]]:= j;
i:= j;
end;
end;
procedure
downheaphql(i: longint); inline;
var
j: longint;
begin
while i> 1 do
begin
j:= i shr 1;
if d[hql[i]]>= d[hql[j]] then
exit;
doicho(hql[i], hql[j]);
vthql[hql[i]]:= i;
vthql[hql[j]]:= j;
i:= j;
end;
end;
procedure
init;
inline;
var
i: longint;
begin
for i:= 1 to n do
begin
inc(nhi);
hmi[nhi]:= i;
vti[i]:= i;
downheapmi(nhi);
inc(nha);
hma[nha]:= i;
vta[i]:= i;
downheapma(i);
17
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
266.
267.
268.
269.
270.
271.
272.
273.
274.
275.
276.
277.
278.
279.
280.
281.
end;
end;
procedure
a_nem(u, v, ii: longint);
var
i, j: longint;
begin
if nhi= 0 then
begin
hoa:= false;
exit;
end;
inline;
i:= hmi[1];
bb[ii]:= i;
hmi[1]:= hmi[nhi];
vti[hmi[1]]:= 1;
dec(nhi);
upheaphmi(1);
j:= vta[i];
hma[j]:= hma[nha];
vta[hma[nha]]:= j;
dec(nha);
downheapma(j);
upheaphma(j);
inc(nhql);
hql[nhql]:= i;
d[hql[nhql]]:= u+ v;
vthql[i]:= nhql;
downheaphql(nhql);
end;
procedure
b_nem(u, v, ii: longint);
var
i, j: longint;
begin
if nha= 0 then
begin
hoa:= false;
exit;
end;
inline;
i:= hma[1];
bb[ii]:= i;
hma[1]:= hma[nha];
vta[hma[1]]:= 1;
dec(nha);
upheaphma(1);
j:= vti[i];
hmi[j]:= hmi[nhi];
vti[hmi[j]]:= j;
dec(nhi);
upheaphmi(j);
downheapmi(j);
18
282.
283.
284.
285.
286.
287.
288.
289.
290.
291.
292.
293.
294.
295.
296.
297.
298.
299.
300.
301.
302.
303.
304.
305.
306.
307.
308.
309.
310.
311.
312.
313.
314.
315.
316.
317.
318.
319.
320.
321.
322.
323.
324.
325.
326.
327.
328.
329.
330.
331.
332.
333.
334.
335.
336.
337.
338.
339.
340.
inc(nhql);
hql[nhql]:= i;
vthql[i]:= nhql;
d[hql[nhql]]:= u+ v;
downheaphql(nhql);
end;
procedure
pop(var u: longint);
begin
u:= hql[1];
hql[1]:= hql[nhql];
dec(nhql);
vthql[hql[1]]:= 1;
upheaphql(1);
end;
inline;
procedure
process; inline;
var
i, j, time, xoay: longint;
begin
sort(1, m);
init;
hoa:= true;
alice:= true;
for i:= 1 to m do
begin
if nhql> 0 then
begin
while (nhql> 0)and (d[hql[1]]<= a[i]. time) do
begin
pop(j);
inc(nhi);
hmi[nhi]:= j;
vti[j]:= nhi;
downheapmi(nhi);
inc(nha);
hma[nha]:= j;
vta[j]:= nha;
downheapma(nha);
end;
end;
if a[i]. ten= 'A' then
begin
inc(slA);
a_nem(a[i]. time, a[i]. xoay, i);
if not hoa then
begin
alice:= false;
tg:= i;
Tc:= a[i]. time;
exit;
end;
end;
if a[i]. ten= 'B' then
begin
19
341.
342.
343.
344.
345.
346.
347.
348.
349.
350.
351.
352.
353.
354.
355.
356.
357.
358.
359.
360.
361.
362.
363.
364.
365.
366.
367.
368.
369.
370.
371.
372.
373.
374.
375.
376.
377.
378.
379.
380.
381.
382.
383.
384.
385.
386.
387.
388.
389.
390.
391.
392.
inc(slB);
b_nem(a[i]. time, a[i]. xoay, i);
if not hoa then
begin
alice:= true;
tg:= i;
Tc:= a[i]. time;
exit;
end;
end;
end;
end;
procedure
main; inline;
var
i, j: longint;
begin
tg:= a[m].time;
for i:= 1 to nhql do
if tg< d[hql[i]] then
tg:= d[hql[i]];
if hoa then
begin
writeln(g, 'DRAW');
writeln(g, 'Game lasts: ', tg,' minute(s)');
for i:= 1 to m do
begin
if a[i]. ten= 'A' then
writeln(g, 'Alice takes the hole: ', bb[i]);
if a[i]. ten= 'B' then
writeln(g, 'Bob takes the hole: ', bb[i]);
end;
end;
if not hoa then
begin
if alice then
writeln(g, 'Bob loses at his turn: ', slB)
else
writeln(g, 'Alice loses at her turn: ', slA);
writeln(g, 'Game lasts: ', tc,' minute(s)');
end;
end;
BEGIN
openf;
readf;
process;
main;
closef;
END.
6. NKTARDY http://vn.spoj.com/problems/NKTARDY
Ý tưởng: Dùng thuật toán MORE: Sắp xếp các công việc theo thời điểm cuối thực
hiện công việc. Thực hiện vòng lặp Xét các công việc cho đến khi gặp công việc
20
- Xem thêm -