Hướng dẫn giải của Hàng đợi có độ ưu tiên
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const maxn=15010; var h,re:array[1..maxn] of longint; n,dem:longint; procedure update(x:longint); var cha,con:longint; begin inc(n); con:=n; cha:=con shr 1; while (cha>0) and (h[cha]<x) do begin h[con]:=h[cha]; con:=cha; cha:=con shr 1; end; h[con]:=x; end; function pop(val:longint):longint; var cha,con,x:longint; begin while (h[1]=val) and (n>0) do begin pop:=h[1]; x:=h[n]; dec(n); cha:=1; con:=2; while con<=n do begin if (con<n) and (h[con+1]>h[con]) then inc(con); if x>=h[con] then break; h[cha]:=h[con]; cha:=con; con:=cha shl 1; end; h[cha]:=x; end; end; procedure pr; var i,x:longint; c:char; begin while not eof do begin read(c); if c='+' then begin read(x); if n<15000 then update(x); end else x:=pop(h[1]); readln; end; repeat inc(dem); re[dem]:=pop(h[1]); until n=0; writeln(dem); for i:=1 to dem do writeln(re[i]); end; begin pr; end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <iostream> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; #define sz(a) int((a).size()) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i) #define repd(i,n) for(int i = (n)-1; i >= 0; --i ) #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000000 #define N char s[100000]; int main() { #ifndef ONLINE_JUDGE freopen( "input.txt", "r", stdin ); //freopen( "output.txt", "w", stdout ); #endif priority_queue<int> qu; while(gets(s) != NULL) { if( s[0] == '-' ) { if(!qu.empty()) { int mx = qu.top(); while(!qu.empty() && qu.top() == mx) qu.pop(); } } else if(qu.size() < 15000) { qu.push(atoi(s+1)); } } vi res; int prev = INT_MAX; for(;!qu.empty(); qu.pop()) { if(qu.top() != prev) res.pb(prev = qu.top()); } printf("%d\n", res.size()); tr(res,it) printf("%d\n", *it); return 0; }
Code mẫu của ladpro98
#include <iostream> using namespace std; const int N = 2e5; struct Heap { int a[N]; int size; Heap() { size = 0; } int top() { return a[1]; } void pop() { a[1] = a[size]; a[size--] = 0; down(1); } void push(int v) { a[++size] = v; up(size); } void up(int v) { if (v == 1) return; int p = v / 2; if (a[p] < a[v]) { swap(a[p], a[v]); up(p); } } void down(int u) { if (u * 2 > size) return; int v = u * 2; if (a[v + 1] > a[v]) v += 1; if (a[u] < a[v]) { swap(a[u], a[v]); down(v); } } } heap; int ans[N]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); char cmd; while (cin >> cmd) { if (cmd == '+') { int v; cin >> v; if (heap.size < 15000) heap.push(v); } else { int v = heap.top(); while (heap.size && heap.top() == v) heap.pop(); } } int n = 0; for (int v = -1; heap.size; heap.pop()) { if (heap.top() != v) ans[++n] = (v = heap.top()); } cout << n << '\n'; for (int i = 1; i <= n; ++i) cout << ans[i] << '\n'; return 0; }
Code mẫu của RR
{$MODE OBJFPC} var i,cnt,save,tmp,hsize,u:longint; a,h:array[1..30111] of longint; c:char; procedure swap(var a,b:longint); var tmp:longint; begin tmp:=a; a:=b; b:=tmp; end; procedure down(i:longint); var j:longint; begin j:=i shl 1; while (j<=hsize) do begin if (j<hsize) and (h[j+1]>h[j]) then inc(j); if h[j]>h[i] then begin swap(h[i],h[j]); i:=j; j:=i shl 1; end else exit; end; end; procedure up(i:longint); var j:longint; begin j:=i shr 1; while (i>1) and (h[i]>h[j]) do begin swap(h[i],h[j]); i:=j; j:=i shr 1; end; end; procedure push(u:longint); begin inc(hsize); h[hsize]:=u; up(hsize); end; function pop:longint; begin result:=h[1]; swap(h[1],h[hsize]); dec(hsize); down(1); end; begin while not eof do begin read(c); if c='+' then begin readln(u); if hsize<15000 then push(u); end else begin readln; if hsize>0 then begin u:=h[1]; while (hsize>0) and (h[1]=u) do tmp:=pop; end; end; end; save:=1000111000; while hsize>0 do begin u:=pop; if u<>save then begin inc(cnt); a[cnt]:=u; save:=u; end; end; writeln(cnt); for i:=1 to cnt do writeln(a[i]); end.
Code mẫu của hieult
#include<iostream> //#include<conio.h> #include<algorithm> #include<vector> #include<string.h> using namespace std; vector<long> a; int main() { string st; char ch; long x,i,t=0; //freopen("qbheap.inp","r",stdin); while((cin>>ch)>0) { if (ch == '+') { cin>>x; if (a.size()<15000) { a.push_back(x); push_heap(a.begin(),a.end()); } } else if (a.size() > 0) { x = a[0]; while (x==a[0]&&a.size()>0) { pop_heap(a.begin(),a.end()); a.pop_back(); } } } sort_heap(a.begin(),a.end()); for (i=a.size()-1;i>=1;i--) if (a[i] != a[i-1]) { t++; } printf("%ld\n",t+1); for (i=a.size()-1;i>=1;i--) if (a[i] != a[i-1]) { printf("%ld\n",a[i]); } printf("%ld",a[0]); //getch(); }
Code mẫu của ll931110
Program QBHEAP; Const input = ''; output = ''; Var heap,a: array[0..15000] of longint; nHeap: integer; Procedure update(v: longint); Var parent,child: integer; Begin inc(nHeap); heap[nHeap]:= v; child:= nHeap; parent:= child div 2; While (parent > 0) and (heap[parent] < v) do Begin heap[child]:= heap[parent]; child:= parent; parent:= child div 2; End; heap[child]:= v; End; Function get: longint; Begin get:= heap[1]; End; Procedure pop; Var r,c,v,t: longint; Begin heap[1]:= heap[nHeap]; dec(nHeap); r:= 1; v:= heap[r]; While r * 2 <= nHeap do Begin c:= r * 2; If (c < nHeap) and (heap[c + 1] > heap[c]) then inc(c); If v >= heap[c] then break; heap[r]:= heap[c]; r:= c; End; heap[r]:= v; End; Procedure solve; Var f: text; v: longint; ch: char; Begin nHeap:= 0; Assign(f, input); Reset(f); While not eof(f) do Begin Read(f, ch); If ch = '+' then Begin Readln(f, v); If nHeap < 15000 then update(v); End else if ch = '-' then Begin v:= get; While (v = get) and (nHeap > 0) do pop; Readln(f); End; End; Close(f); End; Procedure heapsort; Var f: text; i,num: integer; Begin Assign(f, output); Rewrite(f); num:= 0; a[0]:= -1; For i:= nHeap downto 1 do Begin If a[num] <> get then Begin inc(num); a[num]:= get; End; pop; End; Writeln(f, num); For i:= 1 to num do writeln(f, a[i]); Close(f); End; Begin solve; heapsort; End.
Code mẫu của khuc_tuan
#include <stdio.h> #include <iostream> #include <set> using namespace std; multiset<int> se; int a[15000], na; int main() { char s[100]; while(gets(s)) { if(s[0]=='-') { if(se.size()>0) { multiset<int> :: iterator i = se.end(); --i; se.erase( *i ); } } else { int x; sscanf(s+1, "%d", &x); if(se.size()<15000) se.insert(x); } } for(set<int> :: reverse_iterator p = se.rbegin(); p!=se.rend(); ++p) a[na++] = *p; int n = na==0?0:1; for(int i=1;i<na;++i) if(a[i]!=a[i-1]) a[n++] = a[i]; printf("%d\n", n); for(int i=0;i<n;++i) printf("%d\n", a[i]); return 0; }
Bình luận