CÁCH sử DỤNG HÀNG đợi ưu TIÊN (PRIORITY QUEUE) TRONG THƯ VIỆN STL của c++

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (309.34 KB, 14 trang )

CÁCH SỬ DỤNG HÀNG ĐỢI ƯU TIÊN (PRIORITY QUEUE) TRONG THƯ
VIỆN STL CỦA C++
Chuyên đề trình bày cách khai thác hàng đợi ưu tiên (priority queue) trong thư viện
STL của C++ và áp dụng vào một số bài tốn. Tơi viết chuyên đề này nhằm mục đích
là tài liệu tham khảo cho một số trường đang trong giai đoạn chuyển dạy ngơn ngữ
lập trình Free Pascal sang ngơn ngữ C++.
1. Giới thiệu priority_queue:
Priority queue là một loại container adaptor, được thiết kế đặc biệt để phần tử ở đỉnh luôn
luôn là phần tử có độ ưu tiên lớn nhất so với các phần tử khác. Nó giống như một heap, mà
ở đây là heap max, tức là phần tử có độ ưu tiên lớn nhất có thể được lấy ra và các phần tử
khác được chèn vào bất kì.

Độ ưu tiên có thể sử dụng các phép toán trong thư viện functional hoặc có thể tự định
nghĩa.Phép tốn so sánh mặc định khi sử dụng priority queue là phép toán less.
Một số phép tốn so sánh của thư viện functional:
equal_to

Bằng (==)

not_equal_to

Khơng bằng (!=)

greater

Lớn hơn (>)

less

Nhỏ hơn (<)

greater_equal

Lớn hơn hoặc bằng (>=)

less_equal

Nhỏ hơn hoặc bằng (<=)

Để sử dụng priority queue một cách hiệu quả, tùy vào từng bài toán ta viết hàm so sánh để
sử dụng cho linh hoạt.

2. Khai báo priority_queue
Trong C++ khơng có thư viện priority_queue, do đó, để sử dụng priority_queue, ta cần khai
báo thư viên queue:
#include <queue>
2.1. Khai báo với phép toán mặc định là less
1

priority_queue <int> myPriorityQueue;
Ta có thể tưởng tượng priority_queue tương tự như stack, do đó, phần tử có độ ưu tiên lớn
nhất sẽ nằm về phía bên phải (Như hình ảnh ở phần giới thiệu priority_queue). Do đó, khi
sử dụng phép toán less, phần tử độ ưu tiên cao nhất là phần tử có giá trị lớn nhất.
2.2. Khai báo với phép tốn khác

Ví dụ: Sử dụng phép toán greater của thư viện functional
priority_queue myPriorityQueue ;
Khi sử dụng phép toán greater, phần tử độ ưu tiên cao nhất là phần tử có giá trị nhỏ nhất.
2.3. Khai báo sử dụng class so sánh tự định nghĩa

Ta sử dụng một struct kết hợp với nạp chồng toán tử dấu ngoặc đơn như ví dụ bên dưới:
1
2
3
4
5
6
7

struct cmp{
bool operator() (int a,int b) {return a};
int main() {
…
priority_queue q;
}

3. Các phương thức thành viên
size()

Trả về số lượng phần tử của priority_queue

empty()

Trả về true(1) nếu priority_queue rỗng,
ngược lại là false (0)

top()

Truy xuất phần tử ở đỉnh priority_queue

(phần tử có độ ưu tiên lớn nhất)

push (const x)

Thêm phần tử có giá trị x vào
priority_queue. Kích thước priority_queue
tăng thêm 1.

pop ()

Loại bỏ phần tử ở đỉnh priority_queue. Kích
thước priority_queue giảm đi 1.

size()
Trả về số lượng phần tử của priority_queue.
Ví dụ: Tạo một priority_queue có 5 phần tử bất kì và in ra số lượng phần tử của
priority_queue này.
1 #include <iostream>
2 #include <queue>
3 using namespace std;

2

4 int main()
5 {
6
priority_queue<int> myPriorityQueue;
7
for(int i =0 ; i < 5; i++) {

8
myPriorityQueue.push(100) ; // 100 100 100 100 100
9
}
10
cout << “The size of priority_queue is: ” << myPriorityQueue.size()<< endl;
11
return 0;
12 }

Lưu ý:
Tương tự như stack, queue, ta không thể khai báo:
1 priority_queue<int>myPriorityQueue(5) ;

để khai báo 5 phần tử rỗng tương tự như vector hay list vì priority_queue khơng cho phép ta
khai báo phần tử rỗng.
Tương tự, ta không thể khai báo:
1 priority_queue <int> myPriorityQueue (5,100)

để khai báo 5 phần tử của priority_queue có giá trị 100.

empty()
Trả về true(1) nếu priority_queue rỗng, ngược lại là false (0)
Ví dụ: Kiểm tra priority_queue có rỗng khơng và in ra thơng báo tương ứng.
1
2
3
4
5
6

7
8
9
10
11
12
13
14

#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> myPriorityQueue ;
if( myPriorityQueue.empty()) {
cout<<“priority_queue is empty! “<}
else {
cout<<“priority_queue is not empty! “<}
return 0;
}

top()
Truy xuất phần tử ở đỉnh priority_queue (phần tử có độ ưu tiên lớn nhất)
Ví dụ 1: Tạo priority_queue có 5 phần tử có giá trị lần lượt là 5,3,2,4,1 với độ ưu tiên mặc
định. Hãy in ra các phần tử theo thứ tự độ ưu tiên cao nhất đến thấp nhất.
1
2

3
4
5
6
7

#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> myPriorityQueue ;
// creat priority_queue

3

8
9
10
11
12
13
14
15
16
17
18
19 }

myPriorityQueue.push(5) ;
myPriorityQueue.push(3) ;
myPriorityQueue.push(2) ;
myPriorityQueue.push(4) ;
myPriorityQueue.push(1) ;
// print priority_queue
while(!myPriorityQueue.empty()) {
cout<myPriorityQueue.pop() ;
}
return 0;

Nhận xét: Mặc dù thứ tự ta cho vào priorty_queue là 5,3,2,4,1 không được sắp xếp, tuy
nhiên, khi in ra kết quả, ta có thứ tự giảm dần 5,4,3,2,1(Độ ưu tiên là in số lớn nhất, vì độ ưu
tiên mặc định là less).
Ví dụ 2: Tạo priority_queue có 5 phần tử có giá trị lần lượt là 5,3,2,4,1 với độ ưu tiên là
greater. Hãy in ra các phần tử theo thứ tự độ ưu tiên cao nhất đến thấp nhất.
1
2
3
4
5
6
7
8
9
10
11
12
13

14
15
16
17
18

#include <queue>
using namespace std;
int main()
{
priority_queue myPriorityQueue ;
// creat priority_queue
myPriorityQueue.push(5) ;
myPriorityQueue.push(3) ;
myPriorityQueue.push(2) ;
myPriorityQueue.push(4) ;
myPriorityQueue.push(1) ;
// print priority_queue
while(!myPriorityQueue.empty()) {
cout<myPriorityQueue.pop() ;
}
return 0;
}

Nhận xét:Kết quả in ra theo thứ tự tăng dần 1,2,3,4,5 vì độ ưu tiên là greater (lớn hơn).
Ví dụ 2: Tạo priority_queue có 5 phần tử có giá trị lần lượt là 5,3,2,4,1 với độ ưu tiên được
mô tả bởi phương thức so sánh :
1 struct cmp{
2

3 bool operator() (int a,int b) {return a4
5 };

Hãy in ra các phần tử theo thứ tự độ ưu tiên cao nhất đến thấp nhất.

4

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

#include <iostream>
#include <queue>
using namespace std;
struct cmp{
bool operator() (int a,int b) {
return a}
};
int main()
{
priority_queue myPriorityQueue ;
// creat priority_queue
myPriorityQueue.push(5) ;
myPriorityQueue.push(3) ;
myPriorityQueue.push(2) ;
myPriorityQueue.push(4) ;
myPriorityQueue.push(1) ;
// print priority_queue
while(!myPriorityQueue.empty()) {
cout<myPriorityQueue.pop() ;
}
return 0;

}

push (const x)
Thêm phần tử có giá trị x vào priority_queue. Kích thước priority_queue tăng thêm 1.
Ví dụ:
Viết chương trình cho người dùng nhập vào kích thước priorty_queue và nhập vào giá trị
các phần tử. In các phần tử trong priority_queue.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> myPriorityQueue;
int n; // size of queue
cout<<“Size: ” ;
cin>>n ;
// create queue
int tempNumber ;
for(int i = 0 ; icin>>tempNumber ;
myPriorityQueue.push(tempNumber) ;
}
// print queue
for(int i = 0 ; itempNumber = myPriorityQueue.top() ;
myPriorityQueue.pop();
cout<}
return 0;
}

5

pop ()
Loại bỏ phần tử ở đình priority_queue (phần tử cuối cùng được thêm vào priority_queue).

Kích thước priority_queue giảm đi 1.
Ví dụ: Viết chương trình cho người dùng nhập vào kích thước priority_queue và nhập vào
giá trị các phần tử. Sau đó, loại bỏ đi một nửa các phần tử ở đỉnh priority_queue.
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 int main()
5 {
6
priority_queue<int> myPriorityQueue;
7
int n; // size of priority_queue
8
cout<<“Size: ” ;
9
cin>>n ;
10
// create priority_queue
11
int tempNumber ;
12
for(int i = 0 ; i13
cin>>tempNumber ;
14
myPriorityQueue.push(tempNumber ) ;
15
}
16
// delete element

17
for(int i = 0 ; i18
myPriorityQueue.pop() ;
19
}
20
// print priority_queue
21
n = myPriorityQueue.size() ; // after using pop(), the size of priority_queue < n
22
for(int i = 0 ; i23
tempNumber = myPriorityQueue.top() ;
24
myPriorityQueue.pop();
25
cout<26
}
27
return 0;
28 }

4. Một số dạng bài tập có sử dụng priority_queue
Bài1. Dijkstra – Tìm đường đi ngắn nhất trên đồ thị
Mục đích: Từ một đỉnh S, ta muốn biết độ dài đường đi ngắn nhất từ S đến tất cả các đỉnh
cịn lại (trong đồ thị có hướng hoặc vô hướng).
Độ phức tạp : O (n log n).
1 #include <stdio.h>

2 #include <vector>
3 #include <queue>
4 using namespace std;
5
6 const int oo = 1000111000;
7 typedef pair<int, int> ii;
8
9 vector <ii> a[2309];
10 int n, m;
11
12 int d[2309];
13

6

14 void dijkstra(){
15
priority_queue pq;
16
int i, u, v, du, uv;
17
18
for (i=1; i<=n; i++) d[i] = oo;
19
d[1] = 0;
20
pq.push(ii(0, 1));
21
22

while (pq.size()){
23
u=pq.top().second;
24
du=pq.top().first;
25
pq.pop();
26
if (du!=d[u]) continue;
27
28
for (i=0; v=a[u][i].second; i++)
29
{
30
uv=a[u][i].first;
31
if (d[v]>du+uv) {
32
d[v]=du+uv;
33
pq.push(ii(d[v], v));
34
}
35
}
36
}
37
38 }

39
40 main(){
41
int p, q, i, m, w;
42
scanf(“%d%d”, &n, &m);
43
while (m–){
44
scanf(“%d%d%d”, &p, &q, &w);
45
a[p].push_back(ii(w, q));
46
a[q].push_back(ii(w, p));
47
}
48
for (i=1; i<=n; i++) a[i].push_back(ii(0,0));
49
dijkstra();
50
for (i=1; i<=n; i++) printf(“d( 1 -> %d ) = %d\n”, i, d[i]);
51 }

Sample Input

Sample Output

55

d( 1->1 ) = 0

1 2 10

d( 1->2 ) = 10

1 3 10

d( 1->3 ) = 10

2 4 20

d( 1->4 ) = 30

3 4 25

d( 1->5 ) = 1000111000

1 4 33

Bài 2. Tìm cây khung nhỏ nhất của đồ thị bằng thuật toán Prim
Độ phức tạp: O((n+m) log n).
1
2
3
4
5
6

#include <stdio.h>

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

7

7
8 typedef pair<int, int> ii;
9 const int N=100005, oo=0x3c3c3c3c;
10 int n, m, d[N];
11 vector<int> a[N], b[N];
12
13 int prim(int u) {
14
int Sum = 0;
15
priority_queue<ii> qu;
16
for (int i=1; i<=n; i++) d[i]=oo;
17
qu.push(ii(0, u)); d[u]=0;
18
19
while (qu.size()) {
20
ii Pop=qu.top(); qu.pop();
21

int u=Pop.second, du=-Pop.first;
22
if (du!=d[u]) continue;
23
Sum+=d[u]; d[u]=0;
24
25
for (int i=0; int v=a[u][i]; i++)
26
if (d[v] > b[u][i]) {
27
d[v]=b[u][i];
28
qu.push(ii(-d[v], v));
29
}
30
}
31
return Sum;
32 }
33
34 main() {
35
scanf(“%d%d”, &n, &m);
36
for (int i=1; i<=m; i++) {
37
int x, y, z;
38

scanf(“%d%d%d”, &x, &y, &z);
39
a[x].push_back(y);
40
b[x].push_back(z);
41
a[y].push_back(x);
42
b[y].push_back(z);
43
}
44
for (int i=1; i<=n; i++)
45
a[i].push_back(0);
46
cout << prim(1) << endl;
47 }

Mô tả
1. int d[]
d[u] là khoảng cách từ nút u đến cây khung đang xây dựng, d[u]=0 khi u đã được cho vào
cây khung.
2. vector<int> a[]
a[u] là danh sách kề của đỉnh u, kết thúc với số 0
3. vector<int> b[]
b[u][i] là trọng số của cạnh thứ i trong danh sách kề đỉnh u
4. int prim()
trả về trọng số của cây khung nhỏ nhất
Tham khảo

http://vn.spoj.com/problems/QBMST/
8

http://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_Prim
Bài 3. Robot (Đề thi chọn đội tuyển quốc gia chuyên Trần Phú Hải Phòng 2014)
HD vừa sáng tạo ra một trò chơi điều khiển robot mới cho 2 bé Bi, Bo chơi. Nội dung trị chơi như
sau:
–

–

Có N cây cột đánh số từ 1 đến N, cây cột thứ � có chiều cao ℎ[�](�)
Có M đường nhảy dạng �, �, � tương ứng là nhảy từ cây � sang cây � (hoặc từ cây j sang cây
i) mất �(�) và nếu nhảy từ độ cao ℎ (ℎ∈ Ν, ℎ ≤ ℎ[�]) của cây � thì sang cây � sẽ có độ cao là
ℎ − � với điều kiện 0 ≤ ℎ − � ≤ ℎ[�]
Nếu robot di chuyển lên xuống trên cột hiện tại, thời gian di chuyển mất 1(�) trên 1� di
chuyển.

Hiện tại robot đang ở độ cao X của cây 1, Bi-Bo cần phải tìm phương án di chuyển nhanh nhất
đếnđộ cao ℎ[�] của cây N. Bạn hãy giúp 2 bé Bi-Bo tính thời gian di chuyển ngắn nhất thỏa mãn
yêucầu đầu bài?
Dữ liệu: Vào từ file văn bản ROBOT.INP
–

–

–

Dòng 1: Chứa 3 số nguyên dương N, M, X tương ứng là số lượng cây cột, số lượng đường

nhảy và độ cao của robot đang ở cột 1. (2 ≤ � ≤ 100.000; 1 ≤
� ≤ 300.000; 0 ≤ � ≤ℎ[1])
N dòng tiếp theo, dòng thứ � chứa 1 số nguyên dương ℎ[�]
tương ứng là chiều cao của cột �(1 ≤ ℎ[�] ≤ 1.000.000.000 ∀� =
1. . �).
M dòng tiếp theo, mỗi dòng chứa 3 số nguyên dương �, �, �
tương ứng là nhảy từ cây � sang cây � (hoặc từ cây � sang cây �)
mất �(�) (1 ≤ � ≤ 1.000.000.000).

Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.
Kết quả: Ghi ra file văn bản ROBOT.OUT
–

Ghi một số duy nhất là thời gian ngắn nhất để robot di chuyển đến độ cao ℎ[�] của cây N,
nếu không thể di chuyển đến thì ghi -1.

Ví dụ:
ROBOT.INP
550
50
100
25
30
10
1 2 10
2 5 50
2 4 20
431
5 4 20

ROBOT.OUT
110

210
11

-1

Giải thích
Trèo lên 50(m) ở cây 1 mất 50(s)
Nhảy từ cây 1 sang cây 2:
– Mất 10(s)
– ở độ cao 40 trên cây 2
Nhảy từ cây 2 sang cây 4:
– Mất 20(s)
– ở độ cao 20 trên cây 4
Nhảy từ cây 4 sang cây 5:
– Mất 20(s)
– ở độ cao 0
– trèo thêm 10(m) mất 10(s)
Tổng thời gian: 110(s).
Từ cây 1, bất kỳ độ cao nào, khi nhảy
sang cây 2đều khơng thực hiện được vì ℎ
9

12
43
50
10

20
50
12
23
34

100
30

100

10
10
10

− �< 0.
Di chuyển xuống 10(m) ở cây 1 mất 10 (s)
vàđang ở độ cao 20(m)
Nhảy sang cây 2:
– Mất 10(s)
– ở độ cao 10 trên cây 2.
Nhảy sang cây 3:
– Mất 10(s)
– Ở độ cao 0(m), trèo lên 10(m) mất 10(s),
ở độ cao 10(m);
Nhảy sang cây 4:
– Mất 10(s),
– ở độ cao 0 (m), trèo lên 50(m) mất 50(s)
Tổng thời gian: 100(s).

Chương trình:
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

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXN = 100005;
const long long INF = 100001000010000100ll; // >> 10^9*10^5
int H[MAXN];
long long dist[MAXN];
vector<int> to[MAXN], cost[MAXN];
struct Dat{
long long d;
int v;
Dat(long long d, int v):d(d),v(v){}
bool operator<(const Dat& a)const{ return d < a.d;}
};

int main(){
int N, M, X, A, B, T;
scanf(“%d%d%d”,&N,&M,&X);
for(int i = 1; i <= N; i++) scanf(“%d”,&H[i]);
for(int i = 0; i < M; i++){
scanf(“%d%d%d”,&A,&B,&T);
to[A].push_back(B);
cost[A].push_back(T);
to[B].push_back(A);
cost[B].push_back(T);
}
for(int i = 1; i <= N; i++) dist[i] = -INF;
priority_queue<Dat> q;
q.push(Dat(X,1));
while(!q.empty()){
Dat now = q.top(); q.pop();
if(dist[now.v] != -INF) continue;
dist[now.v] = now.d;
for(int i = 0; i < to[now.v].size(); i++){

10

43
44
45
46
47
48
49

50
51
52
53 }

}

int u = to[now.v][i], c = cost[now.v][i];
if(c > H[now.v]) continue;
q.push(Dat(min(now.d-c, (long long)H[u]), u));

}
if(dist[N] == -INF) puts(“-1”);
else printf(“%lld\n”,X+H[N]-dist[N]*2);
return 0;

Bài 4. Hospital (Đề thi chọn đội tuyển quốc gia chuyên Trần Phú Hải Phòng 2014)
Sau 1 năm học vất vả nơi xa xơi, TA trở về q nhà. Để có thêm kinh nghiệm làm việc, TA xin 1
khóa thực tập hè 3 tháng tại bệnh viện thành phố nơi bạn gái anh là TH đang làm việc. Khoa cấp
cứu nơi anh làm việc hằng ngày có rất nhiều bệnh nhân được đưa tới trong khi số lượng phịng chữa
trị có hạn. Các bệnh nhân phải đợi khi nào có phịng khám trống thì mới được chữa trị.
Nhiệm vụ của anh là sắp xếp bệnh nhân có độ nguy kịch cao nhất khi có 1 phịng khám trống.
Mỗi bệnh nhân khi được đưa vào khoa cấp cứu tại thời điểm �0 có độ nguy kịch ban đầu là �[�0], và
tỉ lệ tăng độ nguy kịch theo thời gian là �. Khi đó tại thời điểm �, độ nguy kịch của bệnh nhân này là
�[�] = �[�0] + � . (� – �0).
Khi 1 phòng khám trống yêu cầu bệnh nhân vào thời điểm t, TA phải tìm ra bệnh nhân có độ nguy
kịch lớn nhất vào thời điểm này, để được điều trị kịp thời. Nếu có nhiều bệnh nhân có cùng độ nguy
kịch, chọn bệnh nhân có tỉ lệ tăng độ nguy kịch theo thời gian là lớn nhất.
Đảm bảo rằng ln có bệnh nhân đang chờ khi có phịng khám trống.
Hãy giúp TA xử lý bài toán này nhé.

Dữ liệu: Vào từ file văn bản HOSPITAL.INP
–

Dòng đầu là số lượng bộ dữ liệu T (� ≤ 5).

–

Tiếp theo là các bộ test, mỗi bộ test bao gồm:


Dòng đầu tiên là số nguyên dương N (N ≤ 105) là số lượng bệnh nhân đưa vàophịng cấp
cứu và số lần có phịng khám trống yêu cầu bệnh nhân.



N dòng tiếp theo, mỗi dịng là 1 sự kiện:
o Nếu có bệnh nhân chuyển tới khoa cấp cứu, dòng sẽ chứa ký tự ‘P’ và 3 số nguyên
�0, �[�0], � miêu tả bệnh nhân như đề bài. (0 ≤ �0 ≤ 106; 0 ≤ �[�0] ≤ 108; 0 ≤ � ≤ 100)
o Nếu có phòng khám trống yêu cầu bệnh nhân, dòng sẽ gồm ký tự ‘A’ và số nguyên �
là thời điểm phòng khám yêu cầu.

Biết rằng bệnh nhân và phòng khám yêu cầu sẽ được cung cấp theo thứ tự thời gian xảy ra, tức là
�0và � sẽ tăng dần.
Các số trên một dòng của input file được ghi cách nhau bởi dấu cách.
Kết quả: Ghi ra file văn bản HOSPITAL.OUT
–

Với mỗi bộ dữ liệu:


Dòng đầu tiên ghi “Case #X:” với X là thứ tự bộ dữ liệu bắt đầu từ 1.
11



Các dòng tiếp theo miêu tả bệnh nhân được đưa vào chữa trị mỗi khi có phịng khám
trống u cầu, gồm 2 số nguyên là độ nguy kịch của bệnh nhân này tại thời điểm này và
tỉ lệ tăng độ nguy kịch theo thời gian.

Ví dụ:

12

HOSPITAL.INP

HOSPITAL.OUT

29

Case #1:

P 10 10 1

35 1

P 30 20 1

95 3

A 35

140 3

P 40 20 2

160 2

P 60 50 3

Case #2:

A 75

18 2

P 80 80 3

41 10

A 100

20 1

A 110
6
P 1 10 2
A5
P 10 10 1

P 11 1 10
A 15
A 20
Chương trình:
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

#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
using namespace std;
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Ford(i,a,b) for(int i=a;i>=b;i–)
#define fi first
#define se second
#define sr(x) (int)x.size()
#define BUG(x) {cout << #x << ” = ” << x << endl;}
#define PR(x,a,b) {cout << #x << ” = “; For(_,a,b) cout << x[_] << ‘ ‘; cout << endl;}
#define Bit(s,i) ((s&(1<<i))>0)
#define Two(x) (1<const int MOD = 1000000007;
const int NMAX = 10000;
const double E = 1e-8;
const double PI = acos(-1);
typedef long long LL;
typedef pair<int,int> pii;
int n,stest;
priority_queue<int> H[101];//Khai báo sử dụng 101 prioriry_queue
void Solve() {

13

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

cin >> stest;
For(test,1,stest) {
cin >> n;
cout << “Case #” << test << “:” << endl;
For(i,0,100) while (!H[i].empty()) H[i].pop();
For(i,1,n) {
char ch;
cin >> ch;
if ( ch==’P’ ) {
int t0,s0,r;
cin >> t0 >> s0 >> r;
H[r].push(s0 – t0*r);
} else {
int t;
int res = -1,pos=-1;
cin >> t;
For(j,0,100) if (!H[j].empty()){
int u = H[j].top();
if ( u + j * t >= res ) {
res = u + j*t;
pos = j;
}
}
H[pos].pop();

cout << res << ” ” << pos << endl;
}
}
}
}
int main() {
freopen(“Hospital.inp”,”r”,stdin);
freopen(“Hospital.out”,”w”,stdout);
ios::sync_with_stdio(false);
Solve();
return 0;
}

Trên đây là các bài toán được giải bằng cách sử dụng hàng đợi ưu tiên (priority queue) trong thư
viện STL của C++. Nhờ ưu điểm là khai báo sử dụng một cách dễ dàng nên lời giải của bài toán
ngắn gọn hơn rất nhiều so với lời giải bằng ngơn ngữ lập trình Pascal.

14

greater_equalLớn hơn hoặc bằng (>=)less_equalNhỏ hơn hoặc bằng (<=)Để sử dụng priority queue một cách hiệu quả, tùy vào từng bài toán ta viết hàm so sánh đểsử dụng cho linh hoạt.2. Khai báo priority_queueTrong C++ khơng có thư viện priority_queue, do đó, để sử dụng priority_queue, ta cần khaibáo thư viên queue:#include 2.1. Khai báo với phép toán mặc định là lesspriority_queue myPriorityQueue;Ta có thể tưởng tượng priority_queue tương tự như stack, do đó, phần tử có độ ưu tiên lớnnhất sẽ nằm về phía bên phải (Như hình ảnh ở phần giới thiệu priority_queue). Do đó, khisử dụng phép toán less, phần tử độ ưu tiên cao nhất là phần tử có giá trị lớn nhất.2.2. Khai báo với phép tốn khácVí dụ: Sử dụng phép toán greater của thư viện functionalpriority_queue