Tài liệu Cấu trúc heap và ứng dụng

  • Số trang: 25 |
  • Loại file: DOC |
  • Lượt xem: 225 |
  • Lượt tải: 0
dinhthithuyha

Đã đăng 3693 tài liệu

Mô tả:

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;          // x là gốc thì làm gì có cha     int pa = x/2;                // cha của x     if(heap[x] > heap[pa]){      // x hơn cha nó nên đi lên         swap(heap[x],heap[pa]);  // đổi chỗ         upheap(pa);              // up cha nó     } } void push(int a)                 // đẩy giá trị a vào {     nh++;                        // tăng số lượng      heap[nh] = a;                // cho a vô     upheap(nh);                  // đẩ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];         // kéo thằng cuối lên x     nh­­;                       // giảm số phần tử      downheap(x);                // cập nhật lại     upheap(x);  } 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; 20. {------------------------------------------------------------------} 3 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); if i<=j then begin -} ----} } 4 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 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; 53. readln(f, n); 6 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. 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; 13. end; 7 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. {-----------------------------------------------------} 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; end; -} 8 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. 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). 1. //uses sysutils; 9 2. const 3. 4. type 5. 6. var 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. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. fi=''; fo=''; pt=record gt: longint; vt: longint; end; heap=array[1..2510] of pt; {t1, t2: tdatetime;} f1, f2: text; pos: array[1..250000] of longint; a: array[1..250000] of pt; heapa, heapb: heap; n, k, seed, add, topa, topb: longint; mul, s: int64; t, it: byte; {------------------------------------------------} procedure swapa(i, j: longint); var tg: pt; begin tg:=heapa[i]; heapa[i]:=heapa[j]; heapa[j]:=tg; pos[heapa[i].vt]:=i; pos[heapa[j].vt]:=j; end; {--------------------------------------------------} procedure upheapa(i: longint); begin if (i=1) or (heapa[i].gt<=heapa[i div 2].gt) then exit; swapa(i, i div 2); upheapa(i div 2); end; {------------------------------------------------------------------} procedure downheapa(i: longint); var j: longint; begin j:=i*2; if j>topa then exit; if (j=heapa[j].gt then exit; swapa(i, j); downheapa(j); end; {------------------------------------------------------------------procedure pusha(i: longint); begin inc(topa); heapa[topa]:=a[i]; pos[a[i].vt]:=topa; upheapa(topa); end; {--------------------------------------------------} procedure popa(i: longint); begin heapa[i]:=heapa[topa]; pos[heapa[i].vt]:=i; dec(topa); upheapa(i); downheapa(i); end; {--------------------------------------} 10 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. 117. 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); if i<=j then 11 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. 176. begin until i>j; sort(L, j); sort(i, h); tg:=a[i]; a[i]:=a[j]; a[j]:=tg; inc(i); dec(j); end; 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 begin 12 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. 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 TYPE = lannem 100000; = 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. end; doicho(hma[i], hma[j]); vta[hma[i]]:= i; vta[hma[j]]:= j; i:= j; 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 END. openf; readf; process; main; closef; 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 -