Priority_queue
- Độ khó
- ★★★★☆ Khó
- Thời lượng
- Khoảng 90 phút
- Học trước
- Stack, Queue, Deque, Sort, pair và comparator
- Chủ đề
- heappriority_queue
- Trạng thái
Kiến thức cơ bản
Vì sao cần priority_queue
Tuần trước, queue phục vụ theo thứ tự đến trước, đi trước. Nhưng ở phòng cấp cứu, bệnh nhân nặng nhất được khám trước dù đến sau. Đó là hàng đợi ưu tiên (priority_queue): mỗi lần lấy ra luôn là phần tử ưu tiên nhất, và mặc định phần tử lớn nhất được ưu tiên.
Em có thể dùng set để làm việc này, nhưng set bỏ đi các số trùng và dài dòng hơn. Còn nếu cứ sắp xếp lại cả dãy sau mỗi lần thêm số thì quá chậm. priority_queue cho phép thêm số mới và lấy số lớn nhất, mỗi việc chỉ mất khoảng log n bước (log n khoảng 17 khi n = 105).
Để dùng, em thêm thư viện: #include <queue>. Các đoạn code dưới đây là phần thân hàm main.
Cấu trúc dữ liệu Priority_queue
Hãy tưởng tượng một chiếc hộp kẹo mà bàn tay luôn chạm được vào gói kẹo to nhất. Em bỏ gói mới vào lúc nào cũng được, hộp tự lo việc đưa gói to nhất lên trên cùng.
push(5), push(9), push(2) pop()
[ 9 ] <- top (lớn nhất) [ 5 ] <- top mới
[ 5 ] [ 2 ] [ 2 ]
(các số bên trong được hộp tự sắp xếp, em chỉ nhìn thấy top)
Khai báo priority_queue
priority_queue<data_type> pq; (ví dụ: priority_queue<int> pq;)
priority_queue<int> pq; // mặc định: số LỚN nhất ở trên cùng
pq.push(5); pq.push(9); pq.push(2);
cout << pq.top() << endl; // 9: số lớn nhất
pq.pop(); // bỏ số 9
cout << pq.top() << " " << pq.size() << endl; // 5 2
while (!pq.empty()) { // lấy lần lượt từ lớn đến bé: 5 rồi 2
cout << pq.top() << " ";
pq.pop();
}
Các tính chất của priority_queue
- Không có chỉ số, không duyệt được bằng for như vector. Muốn xem hết phải lấy ra từng phần tử bằng while (!pq.empty()).
- top() chỉ nhìn, pop() mới bỏ đi và pop() không trả về giá trị. Luôn kiểm tra empty() trước khi gọi top() hoặc pop().
- Mặc định số lớn nhất ở trên cùng. Muốn số nhỏ nhất ở trên cùng thì khai báo như sau (nhớ cặp dấu > cách nhau trong các phiên bản C++ cũ):
priority_queue<int, vector<int>, greater<int>> pq; // số NHỎ nhất ở trên cùng
pq.push(5); pq.push(9); pq.push(2);
cout << pq.top(); // 2
- Với pair, hàng đợi so sánh first trước, nếu bằng nhau mới so sánh second. Rất tiện khi ta gói (độ ưu tiên, thông tin kèm theo) vào một cặp:
priority_queue<pair<int, int>> pq; // so sánh first trước, bằng nhau thì so sánh second
pq.push({3, 10}); pq.push({7, 4}); pq.push({7, 8});
cout << pq.top().first << " " << pq.top().second; // 7 8
// Muốn first nhỏ nhất ở trên cùng:
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq2;
Một số hàm của priority_queue
| push(x) | Cho x vào hàng đợi ưu tiên. |
|---|---|
| top() | Xem phần tử ưu tiên nhất (mặc định là phần tử lớn nhất), không lấy ra. Rỗng mà gọi top() là lỗi. |
| pop() | Bỏ phần tử ưu tiên nhất. Hàm này chỉ bỏ đi, không trả về giá trị. Rỗng mà gọi pop() là lỗi. |
| size() | Số phần tử đang có. |
| empty() | Kiểm tra rỗng: đúng trả về true, sai trả về false. |
Mẫu 1: Ghép hai phần tử nhỏ nhất (min-heap)
Bài toán: có n đoạn dây thừng. Nối hai đoạn dài a và b tốn chi phí a + b và tạo ra một đoạn dài a + b. Cần nối tất cả thành một sợi với tổng chi phí nhỏ nhất. Cách khôn ngoan là luôn nối hai đoạn ngắn nhất trước, vì đoạn ngắn nhất sẽ phải trả phí ít nhất. Sau mỗi lần nối, đoạn mới quay lại hàng chờ nên cần một hộp luôn đưa ra hai đoạn ngắn nhất: min-heap.
dây: 4 3 2 6
nối 2+3 = 5 (phí 5) còn: 4 5 6
nối 4+5 = 9 (phí 9) còn: 6 9
nối 6+9 = 15 (phí 15) còn: 15 tổng phí = 5 + 9 + 15 = 29
priority_queue<long long, vector<long long>, greater<long long>> pq;
for (int i = 0; i < n; i++) { long long x; cin >> x; pq.push(x); }
long long tong = 0;
while (pq.size() > 1) {
long long x = pq.top(); pq.pop(); // hai đoạn ngắn nhất
long long y = pq.top(); pq.pop();
tong += x + y; // chi phí nối
pq.push(x + y); // đoạn mới quay lại hàng chờ
}
cout << tong;
Chú ý dùng long long: tổng chi phí có thể rất lớn khi n = 105 và mỗi đoạn dài tới 109.
Mẫu 2: Giữ k số lớn nhất (heap kích thước k)
Bài toán: tìm số lớn thứ k trong dãy n số, hoặc liệt kê k số lớn nhất. Ta giữ trong min-heap tối đa k số. Số mới vào, nếu hộp có hơn k số thì đuổi số nhỏ nhất ra. Cuối cùng hộp giữ đúng k số lớn nhất, và số trên cùng là số lớn thứ k. Cách này chỉ cần n × log k bước.
priority_queue<int, vector<int>, greater<int>> pq; // giữ k số lớn nhất, số nhỏ nhất của nhóm ở trên
for (int i = 0; i < n; i++) {
int x;
cin >> x;
pq.push(x);
if ((int)pq.size() > k) pq.pop(); // quá k số thì đuổi số nhỏ nhất
}
// pq.top() bây giờ là số lớn thứ k
Mẫu 3: Xếp lịch và đếm phòng (sort kết hợp priority_queue)
Bài toán: có n cuộc họp, cuộc họp i bắt đầu ở s[i] và kết thúc ở e[i]. Cuộc họp bắt đầu đúng lúc cuộc họp khác kết thúc thì được dùng lại phòng. Cần ít nhất bao nhiêu phòng? Ta sắp xếp các cuộc họp theo giờ bắt đầu. Hộp min-heap giữ giờ kết thúc của các phòng đang bận. Cuộc họp mới có giờ bắt đầu từ lúc phòng sớm nhất trống thì dùng lại phòng đó, nếu không thì mở phòng mới.
sort(a.begin(), a.end()); // a[i] = {giờ bắt đầu, giờ kết thúc}, xếp theo giờ bắt đầu
priority_queue<int, vector<int>, greater<int>> endTime; // giờ kết thúc của các phòng đang dùng
for (auto& m : a) {
if (!endTime.empty() && endTime.top() <= m.first) endTime.pop(); // có phòng đã trống: dùng lại
endTime.push(m.second); // phòng này bận đến giờ kết thúc
}
cout << endTime.size(); // số phòng cần dùng
Mở rộng (không bắt buộc): trung vị của dòng số
Trung vị là số đứng giữa khi sắp xếp. Số liệu đến từng số một, sau mỗi số cần biết trung vị. Dùng hai hộp: một max-heap giữ nửa nhỏ và một min-heap giữ nửa lớn của các số đã đến. Nếu hai hộp luôn có số phần tử chênh nhau không quá 1 thì trung vị nằm ở top của hộp lớn hơn. Mỗi số mới được đưa vào đúng hộp, rồi chuyển một số giữa hai hộp nếu hai bên lệch quá 1. Em sẽ gặp lại ý tưởng này ở bài thử thách cuối.
Nhận dạng đề bài
| Dấu hiệu trong đề | Công cụ | Cách làm |
|---|---|---|
| Nhiều lần “lấy số lớn nhất (nhỏ nhất) hiện có” rồi thêm số mới vào | priority_queue | top, pop, push; mỗi thao tác mất log n bước |
| Ghép hai phần tử nhỏ nhất (lớn nhất) thành một | priority_queue | Lấy hai phần tử trên cùng, tính, push kết quả vào lại |
| Tìm số lớn thứ k, k số lớn nhất | min-heap kích thước k | push số mới, nếu quá k phần tử thì pop số nhỏ nhất |
| Xếp lịch: ai ưu tiên cao nhất làm trước, có hạn chót hoặc thời điểm đến | sort + priority_queue | Sắp xếp theo thời gian, hàng ưu tiên giữ các ứng viên đang chờ |
| Cần duyệt hết các phần tử hoặc tra cứu theo giá trị | set hoặc map | priority_queue không duyệt, không tìm kiếm được |
Luyện tập
Bài 1. Hộp kẹo của Gấu Po
Gấu Po có một chiếc hộp kẹo. Mỗi gói kẹo trong hộp ghi số viên kẹo. Gấu Po luôn lấy gói có nhiều kẹo nhất ra ăn. Có q sự kiện: bỏ thêm một gói vào hộp, lấy gói nhiều kẹo nhất ra, hoặc đếm số gói đang có trong hộp.
| Đầu vào | Dòng 1: số nguyên q (1 ≤ q ≤ 105). q dòng sau, mỗi dòng là một trong ba dạng: 1 x: bỏ vào hộp một gói có x viên kẹo (1 ≤ x ≤ 109). 2: lấy gói nhiều kẹo nhất ra. 3: đếm số gói trong hộp. | |
|---|---|---|
| Đầu ra | Với mỗi sự kiện loại 2, in số viên kẹo của gói vừa lấy, hoặc in -1 nếu hộp rỗng. Với mỗi sự kiện loại 3, in số gói trong hộp. | |
| Test | Input | Output |
| 1 | 6 1 5 1 9 1 7 2 3 2 | 9 2 7 |
| 2 | 3 2 3 1 4 | -1 0 |
Bài 2. Xếp hạng bằng hộp ưu tiên
Thỏ có n số điểm và muốn xếp chúng từ nhỏ đến lớn. Thỏ không dùng sort, mà ném hết số vào một hộp ưu tiên rồi lấy ra lần lượt. Hãy làm theo Thỏ.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Các số theo thứ tự tăng dần, cách nhau một dấu cách (các số trùng vẫn được in đủ). | |
| Test | Input | Output |
| 1 | 6 5 2 9 2 7 1 | 1 2 2 5 7 9 |
| 2 | 1 3 | 3 |
Bài 3. Số lớn thứ k
Hổ viết n số lên bảng (có thể trùng nhau). Hổ hỏi: nếu xếp các số theo thứ tự giảm dần thì số ở vị trí thứ k là số nào? Các số trùng nhau vẫn được tính là các vị trí khác nhau.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số ở vị trí thứ k khi xếp giảm dần. | |
| Test | Input | Output |
| 1 | 6 2 5 9 2 9 7 1 | 9 |
| 2 | 5 5 4 8 1 6 3 | 1 |
Bài 4. Nghiền đá
Gấu Po có n viên đá, viên thứ i nặng a[i]. Mỗi lượt, Gấu Po chọn hai viên nặng nhất, nặng x và y (x ≥ y), rồi đập chúng vào nhau. Nếu x = y thì cả hai viên vỡ vụn hết, còn nếu x > y thì viên nặng y vỡ hết và viên nặng x còn lại một mảnh nặng x - y. Gấu Po làm đến khi còn nhiều nhất một viên. Hỏi viên còn lại nặng bao nhiêu?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Cân nặng của viên đá còn lại, hoặc 0 nếu không còn viên nào. | |
| Test | Input | Output |
| 1 | 6 2 7 4 1 8 1 | 1 |
| 2 | 2 5 5 | 0 |
Bài 5. Nối dây thừng
Hổ có n đoạn dây thừng, đoạn thứ i dài a[i]. Nối hai đoạn dài x và y thành một đoạn dài x + y tốn x + y đồng. Hổ muốn nối tất cả các đoạn thành một sợi dây duy nhất với tổng chi phí nhỏ nhất. Hỏi tổng chi phí nhỏ nhất là bao nhiêu?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng chi phí nhỏ nhất (nếu n = 1 thì in 0). | |
| Test | Input | Output |
| 1 | 4 4 3 2 6 | 29 |
| 2 | 1 7 | 0 |
Bài 6. Phòng khám của Thỏ
Phòng khám của Thỏ có một hàng chờ khám. Mỗi bệnh nhân có tên và mức khẩn cấp (số càng lớn càng khẩn cấp). Thỏ luôn khám bệnh nhân khẩn cấp nhất; nếu có nhiều người cùng mức thì khám người đến trước.
| Đầu vào | Dòng 1: số nguyên q (1 ≤ q ≤ 105). q dòng sau, mỗi dòng là một trong hai dạng: 1 ten p: bệnh nhân tên ten (chỉ gồm chữ cái thường, dài không quá 20 ký tự) đến với mức khẩn cấp p (1 ≤ p ≤ 109). 2: Thỏ gọi bệnh nhân tiếp theo vào khám. | |
|---|---|---|
| Đầu ra | Với mỗi sự kiện loại 2, in tên bệnh nhân được gọi, hoặc in EMPTY nếu hàng chờ rỗng. | |
| Test | Input | Output |
| 1 | 7 1 an 2 1 binh 5 1 cuc 5 2 2 1 dao 9 2 | binh cuc dao |
| 2 | 2 2 1 po 1 | EMPTY |
Bài 7. Ăn kẹo mỗi ngày
Thỏ có n gói kẹo, gói thứ i có a[i] viên. Mỗi ngày, Thỏ chọn gói còn nhiều kẹo nhất và ăn một nửa số viên kẹo của gói đó, làm tròn lên (gói có 5 viên thì ăn 3 viên, còn 2 viên). Gói đã hết kẹo thì không còn gì để ăn. Sau k ngày, Thỏ còn lại tất cả bao nhiêu viên kẹo?
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n, k ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng số viên kẹo còn lại sau k ngày. | |
| Test | Input | Output |
| 1 | 3 3 10 3 7 | 8 |
| 2 | 2 5 1 1 | 0 |
Bài 8. Trộn kẹo
Gấu Po có n viên kẹo, viên thứ i có độ ngọt a[i]. Gấu Po muốn mọi viên kẹo đều có độ ngọt ít nhất là K. Mỗi lượt, Gấu Po lấy hai viên kẹo ít ngọt nhất, độ ngọt x (nhỏ nhất) và y (nhỏ thứ hai), trộn thành một viên kẹo mới có độ ngọt x + 2y. Hỏi cần ít nhất bao nhiêu lượt trộn để tất cả đều có độ ngọt ít nhất K? Nếu không thể thì in -1.
| Đầu vào | Dòng 1: hai số nguyên n, K (1 ≤ n ≤ 105; 1 ≤ K ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số lượt trộn ít nhất, hoặc -1 nếu không thể. | |
| Test | Input | Output |
| 1 | 6 7 1 2 3 9 10 12 | 2 |
| 2 | 3 100 1 1 1 | -1 |
Bài 9. Số phòng họp ít nhất
Rừng xanh có n cuộc họp, cuộc họp thứ i bắt đầu vào giờ s[i] và kết thúc vào giờ e[i]. Hai cuộc họp có thể dùng chung một phòng nếu cuộc này kết thúc không muộn hơn lúc cuộc kia bắt đầu (kết thúc đúng lúc bắt đầu cũng được). Hỏi cần ít nhất bao nhiêu phòng họp?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng tiếp theo, mỗi dòng gồm hai số nguyên s[i], e[i] (1 ≤ s[i] < e[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Số phòng họp ít nhất. | |
| Test | Input | Output |
| 1 | 4 1 4 2 5 4 6 7 8 | 2 |
| 2 | 3 1 2 2 3 3 4 | 1 |
Bài tập tự luyện
Bài 1. K số lớn nhất
Hổ có n số và muốn biết k số lớn nhất. Hổ chỉ được dùng một hộp ưu tiên có không quá k phần tử (min-heap kích thước k).
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | k số lớn nhất theo thứ tự giảm dần, cách nhau một dấu cách (số trùng vẫn tính từng số). | |
| Test | Input | Output |
| 1 | 7 3 5 1 9 3 9 7 2 | 9 9 7 |
| 2 | 3 3 1 2 3 | 3 2 1 |
Bài 2. Hai gói kẹo mỗi ngày
Gấu Po có n gói kẹo, gói thứ i có a[i] viên. Mỗi ngày, Gấu Po chọn hai gói có nhiều kẹo nhất (hai gói khác nhau, mỗi gói phải còn ít nhất một viên) và ăn một viên ở mỗi gói. Gấu Po làm đến khi không chọn được hai gói còn kẹo nữa. Hỏi Gấu Po ăn được trong bao nhiêu ngày?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 106). | |
|---|---|---|
| Đầu ra | Số ngày Gấu Po ăn kẹo. | |
| Test | Input | Output |
| 1 | 3 1 1 1 | 1 |
| 2 | 3 2 3 4 | 4 |
| 3 | 2 5 1 | 1 |
Bài 3. Tưới cây
Thỏ trồng n cây, cây thứ i cao a[i]. Mỗi ngày Thỏ tưới cho cây thấp nhất (nếu có nhiều cây thấp nhất thì tưới một cây bất kỳ trong số đó), cây đó cao thêm 1. Sau k ngày, hãy cho biết chiều cao của cây thấp nhất và của cây cao nhất.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n, k ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Hai số cách nhau một dấu cách: chiều cao thấp nhất và cao nhất. | |
| Test | Input | Output |
| 1 | 3 4 1 5 2 | 3 5 |
| 2 | 2 1 7 7 | 7 8 |
Bài 4. Hai đội chiến binh
Đội A có n chiến binh và đội B có m chiến binh, mỗi người có một sức mạnh. Mỗi hiệp, chiến binh mạnh nhất còn lại của đội A (sức mạnh x) đấu với chiến binh mạnh nhất còn lại của đội B (sức mạnh y). Nếu x > y thì chiến binh của B bị loại, chiến binh của A còn sức mạnh x - y và quay lại đội. Nếu x < y thì ngược lại. Nếu x = y thì cả hai bị loại. Trò chơi dừng khi có một đội không còn ai. Hỏi kết quả?
| Đầu vào | Dòng 1: hai số nguyên n, m (1 ≤ n, m ≤ 105). Dòng 2: n số nguyên là sức mạnh đội A. Dòng 3: m số nguyên là sức mạnh đội B (mọi sức mạnh từ 1 đến 109). | |
|---|---|---|
| Đầu ra | Một dòng gồm hai thành phần cách nhau một dấu cách: A nếu đội A thắng (còn người, đội B hết), B nếu đội B thắng, DRAW nếu cả hai đội cùng hết người; theo sau là số chiến binh còn lại của đội thắng (0 nếu hòa). | |
| Test | Input | Output |
| 1 | 3 2 5 3 4 6 2 | A 2 |
| 2 | 1 1 4 4 | DRAW 0 |
Bài 5. Lịch học thêm
Thỏ có n bài học thêm, mỗi bài mất đúng một ngày. Bài thứ i phải học xong không muộn hơn ngày d[i] (ngày 1, 2, 3, ...) và nếu học sẽ được p[i] điểm. Mỗi ngày Thỏ chỉ học một bài. Thỏ có thể bỏ qua bài nào đó. Hỏi tổng điểm lớn nhất Thỏ nhận được?
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng tiếp theo, mỗi dòng gồm hai số nguyên d[i], p[i] (1 ≤ d[i] ≤ 109; 1 ≤ p[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng điểm lớn nhất. | |
| Test | Input | Output |
| 1 | 5 2 50 1 40 2 30 3 20 3 10 | 110 |
| 2 | 2 1 5 1 9 | 9 |
Bài 6. Phục vụ nhanh nhất trước
Quầy phục vụ của Hổ chỉ có một nhân viên. Có n khách, khách i đến vào phút a[i] và cần phục vụ s[i] phút. Khi nhân viên rảnh, nhân viên chọn khách đang chờ có thời gian phục vụ ngắn nhất (bằng nhau thì chọn khách có số thứ tự nhỏ hơn). Nếu không ai đang chờ thì nhân viên đợi khách đến sớm nhất. Hãy tính tổng thời gian chờ của mọi khách (thời gian chờ là khoảng từ lúc khách đến đến lúc bắt đầu được phục vụ).
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng tiếp theo, mỗi dòng gồm hai số nguyên a[i], s[i] (0 ≤ a[i] ≤ 109; 1 ≤ s[i] ≤ 104). | |
|---|---|---|
| Đầu ra | Tổng thời gian chờ. | |
| Test | Input | Output |
| 1 | 4 0 7 2 4 4 1 5 4 | 16 |
| 2 | 2 0 3 10 2 | 0 |
Bài 7. Chọn dự án
Thỏ có số vốn ban đầu W và có n dự án để chọn. Dự án i cần vốn tối thiểu c[i] mới được làm và mang lại lợi nhuận p[i]; làm xong, vốn của Thỏ tăng thêm p[i]. Mỗi dự án chỉ làm được một lần và Thỏ làm tối đa k dự án. Hỏi vốn lớn nhất sau cùng của Thỏ?
| Đầu vào | Dòng 1: ba số nguyên n, k, W (1 ≤ n ≤ 105; 1 ≤ k ≤ n; 0 ≤ W ≤ 109). n dòng tiếp theo, mỗi dòng gồm hai số nguyên c[i], p[i] (0 ≤ c[i] ≤ 109; 1 ≤ p[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Vốn lớn nhất sau khi làm tối đa k dự án. | |
| Test | Input | Output |
| 1 | 3 2 0 0 1 1 2 1 3 | 4 |
| 2 | 2 1 5 10 100 3 4 | 9 |
Bài 8. K cặp có tổng nhỏ nhất
Gấu Po có hai dãy số A và B, mỗi dãy gồm n số. Gấu Po chọn một số của A và một số của B để tạo thành một cặp (hai cặp khác nhau nếu khác vị trí chọn). Hãy liệt kê k cặp có tổng nhỏ nhất, theo thứ tự tăng dần của tổng.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ n ≤ 105; 1 ≤ k ≤ min(n × n, 105)). Dòng 2: n số nguyên của A (1 ≤ A[i] ≤ 109). Dòng 3: n số nguyên của B (1 ≤ B[i] ≤ 109). | |
|---|---|---|
| Đầu ra | k số cách nhau một dấu cách, là k tổng nhỏ nhất theo thứ tự tăng dần. | |
| Test | Input | Output |
| 1 | 3 4 1 7 11 2 4 6 | 3 5 7 9 |
| 2 | 2 4 1 1 1 1 | 2 2 2 2 |
Bài 9. Thử thách (không bắt buộc): Trung vị của dòng số
Gấu Po đọc lần lượt n số. Sau khi đọc mỗi số, Gấu Po muốn biết trung vị của các số đã đọc. Với m số đã đọc, trung vị là số ở vị trí (m + 1) / 2 (chia lấy phần nguyên) khi xếp tăng dần, tức là khi m chẵn thì lấy số ở giữa nhỏ hơn. (Gợi ý: dùng hai hộp ưu tiên, một max-heap giữ nửa nhỏ và một min-heap giữ nửa lớn.)
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | n số cách nhau một dấu cách, số thứ t là trung vị của t số đầu tiên. | |
| Test | Input | Output |
| 1 | 5 5 2 8 1 9 | 5 2 5 2 5 |
| 2 | 3 3 2 1 | 3 2 2 |
-
Gợi ý chung: Mặc định priority_queue<int> đưa số lớn nhất lên trên cùng. Muốn số nhỏ nhất ở trên cùng, hãy khai báo priority_queue<int, vector<int>, greater<int>>. Nếu quên, chương trình vẫn chạy nhưng cho kết quả sai, nên hãy đọc kỹ đề xem mình cần lớn nhất hay nhỏ nhất trước khi khai báo.
-
Lưu ý thêm: Giống stack và queue, priority_queue không có chỉ số, không duyệt được, và phải kiểm tra empty() trước khi gọi top() hoặc pop(). Khi cộng dồn chi phí hoặc nối các số lớn, hãy dùng long long.