Nguồn đề bài: QBHEAP
Nội dung bài viết
1. Đề bài QBHEAP spoj
Cho trước một danh sách rỗng. Người ta xét hai thao tác trên danh sách đó:
Thao tác “+V” (ở đây V là một số tự nhiên <= 1000000000): Nếu danh sách đang có ít hơn 15000 phần tử thì thao tác này bổ sung thêm phần tử V vào danh sách; Nếu không, thao tác này không có hiệu lực.
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; Nếu không, thao tác này không có hiệu lực
Input
Gồm nhiều dòng, mỗi dòng ghi một thao tác. Thứ tự các thao tác trên các dòng được liệt kê theo đúng thứ tự sẽ thực hiện
Output
Dòng 1: Ghi số lượng những giá trị còn lại trong danh sách.
Các dòng tiếp theo: Liệt kê những giá trị đó theo thứ tự giảm dần, mỗi dòng 1 số
Example
Input:
+1
+3
+2
+3
–
+4
+4
–
+2
+9
+7
+8
–
Output:
4
8
7
2
1
2. Code tham khảo QBHEAP spoj pascal, c++
a. Code c++ viết lại heap
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 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 | #include <bits/stdc++.h> using namespace std; int n; vector<int> a; void DownHeap(int p) { int key=a[p]; while(p*2<=n) { int c=p*2; if(c<n && a[c]<a[c+1]) c++; if(a[c]<=key) break; a[p]=a[c]; p=c; } a[p]=key; } void UpHeap(int c) { int key=a[c]; while(c>=2) { int p=c/2; if(a[p]>=key) break; a[c]=a[p]; c=p; } a[c]=key; } void AddHeap(int val) { n++; a[n]=val; UpHeap(n); } void RemoveHeap() { a[1]=a[n]; n--; DownHeap(1); } void Init() { a.resize(15000+100); } void Solve() { char s; int tg; while (scanf("%c",&s) != EOF) { if(s=='+') { scanf("%d",&tg); if(n<15000) AddHeap(tg); } if(s=='-') { if(n>0) tg=a[1]; while(n>0 && tg==a[1]) RemoveHeap(); } } vector<int> b; while(n) { tg=a[1]; if( b.empty() || tg!=b.back()) b.push_back(tg); RemoveHeap(); } cout<<b.size()<<endl; for (int i=0;i<b.size();i++) cout<<b[i]<<endl; } int main() { Init(); Solve(); } |
b. Code Sử dụng thư viện priority queue trong c++
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 46 47 48 | #include <bits/stdc++.h> #include <queue> using namespace std; priority_queue <long, vector<long>, less_equal<long> > heap; long tmp; vector <long> res; string c; int main() { while (cin >> c) { if (c[0]=='+') { c.erase(0,1); tmp = atoi(c.c_str()); if (heap.size()<15000) heap.push(tmp); } else if (c[0]=='-') { if (!heap.empty()) { tmp = heap.top(); while (!heap.empty() && heap.top()==tmp) heap.pop(); } } else break; } while (!heap.empty()) { tmp = heap.top(); while (!heap.empty() && heap.top()==tmp) heap.pop(); res.push_back(tmp); } cout << res.size()<<endl; for (unsigned i=0; i<res.size(); i++) cout << res[i] << endl; return 0; } |
c. Code pascal
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 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 105 106 107 | const fi=''; nmax=15001; type data=longint; var f:text; Heap,B:array[0..nmax+1] of data; nHeap,n:data; procedure swap(a,b:data); var z:data; begin z:=heap[a]; heap[a]:=heap[b]; heap[b]:=z; end; procedure UpHeap(i:data); begin if (i=1) or (heap[i]<=heap[i div 2]) then exit; swap(i,i div 2); upheap(i div 2); end; procedure push(x:data); begin inc(nHeap); heap[nHeap]:=x; upheap(nHeap); end; procedure downheap(i:data); var j:data; begin j:=i*2; if j>nHeap then exit; if (j<nHeap) and (heap[j+1]>heap[j]) then inc(j); if heap[i]>=heap[j] then exit; swap(i,j); downheap(j); end; procedure pop; begin heap[1]:=heap[nHeap]; dec(nHeap); downheap(1); end; procedure xuli; var i,j,x,tmp,res:data; c:char; begin assign(f,fi); reset(f); nheap:=0; while not seekeof(f) do begin read(f,c); if c='+' then begin readln(f,x); if nHeap<15000 then begin push(x); end; end else begin readln(f); if nHeap>0 then begin tmp:=heap[1]; while (nheap>0) and (heap[1]=tmp) do pop; end; end; end; res:=0; while nHeap>0 do begin tmp:=heap[1]; while (nHeap>0) and (heap[1]=tmp) do pop; inc(res); b[res]:=tmp; end; writeln(res); for i:=1 to res do writeln(b[i]); close(f); end; begin xuli; end. |
Bài viết liên quan
- MSE07B spoj – Double Queue
- P167PROE spoj PTIT – ROUND 7E – Phương trình
- PTIT016E spoj PTIT – ACM PTIT 2016 E – Kỳ thi ACM/ICPC
- PTIT016D spoj PTIT- ACM PTIT 2016 D – Biểu thức
- Spoj PTIT PTIT016C – ACM PTIT 2016 C – Chẵn lẻ
- PTIT127A spoj PTIT – Tổ chức kì thi
- P167PROD spoj PTIT – ROUND 7D – ABC
- PBCSEQ SPOJ – Các đoạn nguyên
- VDANGER SPOJ- Nguy hiểm rõ ràng trước mắt
- P164SUMI spoj PTIT – ROUND 4I – Next round