Tạo bài viết
Đăng ký
02/10/2018, 14:00

MSE07B spoj – Double Queue

Nguồn đề bài: http://vn.spoj.com/problems/MSE07B/vn/ 1. Đề bài MSE07B spoj Ngân hàng BIG-Bank mở một chi nhánh ở Bucharest và được trang bị một máy tính hiện đại với các công nghệ mới nhập, C2#,VC3+ … chỉ chuối mỗi cái là không ai biết lập trình. ...

Nguồn đề bài: http://vn.spoj.com/problems/MSE07B/vn/

1. Đề bài MSE07B spoj

Ngân hàng BIG-Bank mở một chi nhánh ở Bucharest và được trang bị một máy tính hiện đại với các công nghệ mới nhập, C2#,VC3+ … chỉ chuối mỗi cái là không ai biết lập trình.

Họ cần một phần mềm mô tả hoạt động của ngân hàng như sau: mỗi khách hàng có một mã số là số nguyên K, và khi đến ngân hàng giao dịch, họ sẽ nhận được 1 số P là thứ tự ưu tiên của họ. Các thao tác chính như sau

0 Kết thúc phục vụ

1 K P Thêm khách hàng K vào hàng đợi với độ ưu tiên P

2 Phục vụ người có độ ưu tiên cao nhất và xóa khỏi danh sách hàng đợi

3 Phục vụ người có độ ưu tiên thấp nhất và xóa khỏi danh sách hàng đợi.

Tất nhiên là họ cần bạn giúp rồi.

Input

Mỗi dòng của input là 1 yêu cầu, và chỉ yêu cầu cuối cùng mới có giá trị là 0. Giả thiết là khi có yêu cầu 1 thì không có khách hàng nào khác có độ ưu tiên là P.

K<=10^6, và P<= 10^7.Một khách hàng có thể yêu cầu phục vụ nhiều lần và với các độ ưu tiên khác nhau.

Output

Với mỗi yêu cầu 2 hoặc 3, in ra trên 1 dòng mã số của khách hàng được phục vụ tương ứng. Nếu có yêu cầu mà hàng đợi rỗng, in ra số 0.

Sample

Input :
2
1 20 14
1 30 3
2
1 10 99
3
2
2
0
Ouput:
0
20
30
10
0

2. Code tham khảo MSE07B spoj

const fi='; nmax=10000000; type data=longint; data1=record gt,vt:data; end; var f:text; Heapmin,Heapmax:array[0..nmax+1] of data1; posmin,posmax:array[0..nmax+1] of data; nheapmin,nheapmax:data; procedure swap(var a,b:data1); var c:data1; begin c:=a; a:=b; b:=c; end; procedure upheapmin(i:data); var j:data; begin if (i=1) or (heapmin[i].gt>=heapmin[i div 2].gt) then exit; posmin[heapmin[i].gt]:=i div 2; posmin[heapmin[i div 2].gt]:=i; swap(heapmin[i],heapmin[i div 2]); upheapmin(i div 2); end; procedure upheapmax(i:data); begin if (i=1) or (heapmax[i].gt<=heapmax[i div 2].gt) then exit; posmax[heapmax[i].gt]:=i div 2; posmax[heapmax[i div 2].gt]:=i; swap(heapmax[i],heapmax[i div 2]); upheapmax(i div 2); end; procedure downheapmin(i:data); var j:data; begin j:=i*2; if j>nheapmin then exit; if (j<nheapmin) and (heapmin[j+1].gt<heapmin[j].gt) then inc(j); if Heapmin[j].gt>=heapmin[i].gt then exit; posmin[heapmin[i].gt]:=j; posmin[heapmin[j].gt]:=i; swap(heapmin[i],heapmin[j]); downheapmin(j); end; procedure downheapmax(i:data); var j:data; begin j:=i*2; if j>nheapmax then exit; if (j<nheapmax) and (heapmax[j+1].gt>heapmax[j].gt) then inc(j); if Heapmax[j].gt<=heapmax[i].gt then exit; posmax[heapmax[i].gt]:=j; posmax[heapmax[j].gt]:=i; swap(heapmax[i],heapmax[j]); downheapmax(j); end; procedure add(k,p:data); begin inc(nheapmin); heapmin[nheapmin].gt:=p; heapmin[nheapmin].vt:=k; posmin [p]:=nheapmin; inc(nheapmax); heapmax[nheapmax].gt:=p; heapmax[nheapmax].vt:=k; posmax [p]:=nheapmax; upheapmax(nheapmax); upheapmin(nheapmin); end; function popmax(v:data):data1; begin popmax:=heapmax[v]; heapmax[v]:=heapmax[nheapmax]; dec(nheapmax); posmax[heapmax[v].gt]:=v; upheapmax(v); downheapmax(v); end; Function PopMin (v : LongInt) : data1; Begin PopMin:=HeapMin[v]; HeapMin[v]:=HeapMin[nHeapmin]; dec(nHeapmin); PosMin[Heapmin[v].gt]:=v; UpheapMin(v); DownheapMin(v); end; procedure docfile; var i,j,q,k,p:data; tmp:data1; begin assign(f,fi); reset(f); nheapmin:=0; nheapmax:=0; repeat read(f,q); if q=0 then break; if q=1 then begin read(f,k,p); add(k,p); end else if q=2 then begin if nheapmax=0 then writeln(0) else begin tmp:=popmax(1); writeln(tmp.vt); popmin(posmin[tmp.gt]); end; end else begin if nheapmin=0 then writeln(0) else begin tmp:=popmin(1); writeln(tmp.vt); popmax(posmax[tmp.gt]); end; end; until false; close(f); end; begin docfile; end.
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
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
const   fi=';
        nmax=10000000;
type    data=longint;
        data1=record
                gt,vt:data;
        end;
 
var
        f:text;
        Heapmin,Heapmax:array[0..nmax+1] of data1;
        posmin,posmax:array[0..nmax+1] of data;
        nheapmin,nheapmax:data;
 
procedure swap(var a,b:data1);
var     c:data1;
begin
        c:=a;
        a:=b;
        b:=c;
end;
 
procedure upheapmin(i:data);
var     j:data;
begin
        if (i=1) or (heapmin[i].gt>=heapmin[i div 2].gt) then exit;
 
        posmin[heapmin[i].gt]:=i div 2;
        posmin[heapmin[i div 2].gt]:=i;
 
        swap(heapmin[i],heapmin[i div 2]);
        upheapmin(i div 2);
end;
 
procedure upheapmax(i:data);
begin
        if (i=1) or (heapmax[i].gt<=heapmax[i div 2].gt) then exit;
        posmax[heapmax[i].gt]:=i div 2;
        posmax[heapmax[i div 2].gt]:=i;
        swap(heapmax[i],heapmax[i div 2]);
        upheapmax(i div 2);
end;
 
procedure downheapmin(i:data);
var     j:data;
begin
        j:=i*2;
        if j>nheapmin then exit;
        if (j<nheapmin) and (heapmin[j+1].gt<heapmin[j].gt) then inc(j);
        if Heapmin[j].gt>=heapmin[i].gt then exit;
        posmin[heapmin[i].gt]:=j;
        posmin[heapmin[j].gt]:=i;
        swap(heapmin[i],heapmin[j]);
        downheapmin(j);
end;
 
 
procedure downheapmax(i:data);
var     j:data;
begin
        j:=i*2;
        if j>nheapmax then exit;
        if (j<nheapmax) and (heapmax[j+1].gt>heapmax[j].gt) then inc(j);
        if Heapmax[j].gt<=heapmax[i].gt then exit;
        posmax[heapmax[i].gt]:=j;
        posmax[heapmax[j].gt]:=i;
        swap(heapmax[i],heapmax[j]);
        downheapmax(j);
end;
 
 
procedure add(k,p:data);
begin
        inc(nheapmin);
        heapmin[nheapmin].gt:=p;
        heapmin[nheapmin].vt:=k;
        posmin [p]:=nheapmin;
 
        inc(nheapmax);
        heapmax[nheapmax].gt:=p;
        heapmax[nheapmax].vt:=k;
 
        posmax [p]:=nheapmax;
 
        upheapmax(nheapmax);
        upheapmin(nheapmin);
end;
 
function popmax(v:data):data1;
begin
        popmax:=heapmax[v];
        heapmax[v]:=heapmax[nheapmax];
        dec(nheapmax);
        posmax[heapmax[v].gt]:=v;
        upheapmax(v);
        downheapmax(v);
end;
 
Function PopMin (v : LongInt) : data1;
         Begin
              PopMin:=HeapMin[v];
              HeapMin[v]:=HeapMin[nHeapmin];
              dec(nHeapmin);
              PosMin[Heapmin[v].gt]:=v;
              UpheapMin(v);
              DownheapMin(v);
         end;
 
 
procedure docfile;
var     i,j,q,k,p:data;
        tmp:data1;
begin
        assign(f,fi); reset(f);
        nheapmin:=0;
        nheapmax:=0;
        repeat
                read(f,q);
                if q=0 then break;
                if q=1 then
                        begin
                                read(f,k,p);
                                add(k,p);
                        end
                else
                        if q=2 then
                                begin
                                        if nheapmax=0 then
                                                writeln(0)
                                        else
                                                begin
                                                        tmp:=popmax(1);
                                                        writeln(tmp.vt);
                                                        popmin(posmin[tmp.gt]);
                                                end;
                                end
                        else
                                begin
                                        if nheapmin=0 then
                                                writeln(0)
                                        else
                                                begin
                                                        tmp:=popmin(1);
                                                        writeln(tmp.vt);
                                                        popmax(posmax[tmp.gt]);
 
 
                                                end;
                                end;
        until false;
        close(f);
end;
 
begin

Hoàng Hải Đăng

24 chủ đề

7226 bài viết

Có thể bạn quan tâm
0
Các chủ đề đang được quan tâm
phần mềm lập trình php | lập trình web php + mysql | khóa học lập trình php | tự học lập trình php | học php cơ bản thachpham | Code24h | Cho thuê phòng trọ hà nội | Cho thuê phòng trọ bình thạnh | Cho thuê phòng trọ | Cho thuê nhà trọ
Đăng ký

Đăng ký nhận thông báo

Các bài học thú vị sẽ được gửi đến inbox của bạn

HỖ TRỢ HỌC VIÊN
VỀ CODE24H
HỢP TÁC VÀ LIÊN KẾT
KẾT NỐI VỚI CHÚNG TÔI
TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI

CCode 24h, code mọi lúc, mọi nơi

© Copy right 2018 - 2024