QBHEAP spoj - Hàng đợi có độ ưu tiên

Nguồn đề bài: QBHEAP

Nội dung bài viết

1. Đề bài QBHEAP spoj
2. Code tham khảo QBHEAP spoj pascal, c++

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

#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();
}

#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++

#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;
}

#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

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.

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;

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.

QBHEAP spoj – Hàng đợi có độ ưu tiên

1. Đề bài QBHEAP spoj

Input

Output

Example

2. Code tham khảo QBHEAP spoj pascal, c++

a. Code c++ viết lại heap

b. Code Sử dụng thư viện priority queue trong c++

c. Code pascal

Bài viết liên quan

Trả lời Hủy