Chuyên đề: Hàng đợi ưu tiên
Điểm: 100
Bạn có ~N~ sợi dây thừng với độ dài khác nhau. Bạn cần nối tất cả chúng lại thành một sợi dây thừng duy nhất. Mỗi lần nối 2 sợi dây, chi phí bạn phải bỏ ra bằng tổng độ dài của 2 sợi dây đó.
Hãy tìm cách nối sao cho tổng chi phí bỏ ra là nhỏ nhất.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 10^5~).
- Dòng thứ hai chứa ~N~ số nguyên dương ~L_1, L_2, ..., L_N~ (~1 \le L_i \le 10^6~) là độ dài của các sợi dây thừng.
Kết quả
In ra một số nguyên duy nhất là tổng chi phí nối dây thừng nhỏ nhất. (Lưu ý: Kết quả có thể vượt quá giới hạn số nguyên 32-bit, hãy sử dụng kiểu dữ liệu 64-bit).
Ví dụ
Input
4
4 3 2 6
Output
29
Giải thích
- Bước 1: Chọn 2 sợi ngắn nhất là
2và3để nối. Chi phí = 5. Các sợi dây còn lại:[4, 6, 5]. - Bước 2: Chọn 2 sợi ngắn nhất là
4và5để nối. Chi phí = 9. Các sợi dây còn lại:[6, 9]. - Bước 3: Nối 2 sợi cuối cùng
6và9. Chi phí = 15. Còn 1 sợi duy nhất. - Tổng chi phí = 5 + 9 + 15 = 29.
Một bệnh viện có ~N~ bệnh nhân đến khám bệnh rải rác trong ngày. Bệnh nhân thứ ~i~ có mã số ~ID_i~, đến viện lúc ~T_i~, cần ~D_i~ khoảng thời gian để bác sĩ khám xong, và có mức độ ưu tiên là ~P_i~ (số càng lớn, ưu tiên càng cao).
Bác sĩ chỉ có một người và bắt đầu làm việc từ thời điểm ~t = 0~. Tại bất kỳ thời điểm nào khi bác sĩ rảnh rỗi, bác sĩ sẽ gọi bệnh nhân đang chờ theo quy tắc sau:
- Chọn người có mức độ ưu tiên ~P_i~ cao nhất.
- Nếu có nhiều người cùng mức ưu tiên, chọn người đến viện sớm nhất (thời điểm ~T_i~ nhỏ nhất).
- Nếu vẫn có nhiều người đến cùng lúc, chọn người có mã số ~ID_i~ nhỏ nhất.
Hãy in ra thứ tự mã số (~ID~) của các bệnh nhân lần lượt được bác sĩ khám.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 10^5~).
- ~N~ dòng tiếp theo, mỗi dòng chứa 4 số nguyên ~ID_i, T_i, D_i, P_i~ cách nhau bởi khoảng trắng. (~1 \le ID_i \le N~, ~0 \le T_i \le 10^9~, ~1 \le D_i \le 10^4~, ~1 \le P_i \le 100~).
- Dữ liệu đảm bảo các ~ID_i~ là phân biệt.
Kết quả
In ra một dòng duy nhất gồm ~N~ số nguyên là thứ tự ~ID~ của các bệnh nhân được khám, cách nhau bởi một khoảng trắng.
Ví dụ
Input
5
1 1 3 1
2 2 2 5
3 3 1 5
4 4 2 2
5 10 2 1
Output
1 2 3 4 5
Giải thích
- Thời điểm
t=1: Bệnh nhânID=1đến. Bác sĩ rảnh ~\rightarrow~ Khám luôn. Khám xong lúct = 1 + 3 = 4. - Trong lúc bác sĩ khám người 1, những người
ID=2,ID=3,ID=4lần lượt đến và phải chờ. - Thời điểm
t=4: Bác sĩ khám xong người 1. Trong hàng đợi lúc này cóID=2, 3, 4.- Người 2 và 3 có ưu tiên cao nhất (~P=5~).
- Người 2 đến sớm hơn (~T=2 < T=3~) ~\rightarrow~ Chọn khám người 2. Khám xong lúc
t = 4 + 2 = 6.
- Thời điểm
t=6: Hàng đợi cóID=3, 4. Khám người 3 (~P=5~). Xong lúct=7. - Thời điểm
t=7: Hàng đợi cóID=4. Khám người 4. Xong lúct=9. - Thời điểm
t=9: Bác sĩ rảnh, nhưng không có ai chờ. - Thời điểm
t=10: Bệnh nhânID=5đến. Bác sĩ khám luôn. - Thứ tự gọi khám:
1 2 3 4 5.
Điểm: 100
Cho mảng ~A~ gồm ~N~ số nguyên và số nguyên dương ~K~. Hãy tìm và in ra ~K~ phần tử lớn nhất của mảng theo thứ tự giảm dần.
Yêu cầu: Hãy cố gắng sử dụng cấu trúc dữ liệu Hàng đợi ưu tiên (Priority Queue) để giải quyết bài toán với bộ nhớ ~O(K)~ thay vì sắp xếp toàn bộ mảng.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ (~1 \le K \le N \le 10^5~).
- Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~-10^9 \le A_i \le 10^9~), cách nhau bởi khoảng trắng.
Kết quả
In ra một dòng duy nhất chứa ~K~ số nguyên lớn nhất theo thứ tự giảm dần, phân cách nhau bởi một khoảng trắng.
Ví dụ
Input
6 3
7 2 9 1 5 8
Output
9 8 7
Giải thích
Ta cần tìm ~K = 3~ phần tử lớn nhất.
Các phần tử lớn nhất trong mảng là ~9, 8, 7~. Khi in ra theo thứ tự giảm dần ta được kết quả là 9 8 7.
Điểm: 100
Cho ~K~ mảng số nguyên, mỗi mảng gồm ~N~ phần tử đã được sắp xếp theo thứ tự tăng dần. Hãy gộp tất cả ~K~ mảng này thành một mảng duy nhất và vẫn đảm bảo thứ tự tăng dần.
Yêu cầu: Khối lượng dữ liệu rất lớn, nếu bạn gộp tất cả rồi mới dùng hàm sort() thì sẽ bị quá thời gian. Hãy thiết kế thuật toán sử dụng Hàng đợi ưu tiên (Priority Queue) để tối ưu.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên dương ~K~ và ~N~ (~1 \le K, N \le 500~).
- ~K~ dòng tiếp theo, mỗi dòng chứa ~N~ số nguyên ~A_{i, j}~ (~-10^9 \le A_{i, j} \le 10^9~), phân cách nhau bởi khoảng trắng, đại diện cho một mảng đã được sắp xếp tăng dần.
Kết quả
In ra một dòng duy nhất chứa ~K \times N~ số nguyên của mảng sau khi đã gộp, phân cách nhau bởi một khoảng trắng.
Ví dụ
Input
3 4
1 4 7 10
2 5 8 11
3 6 9 12
Output
1 2 3 4 5 6 7 8 9 10 11 12
Giải thích
Có 3 mảng, mỗi mảng 4 phần tử. Lấy lần lượt các phần tử nhỏ nhất từ đầu các mảng ta sẽ thu được dãy tăng dần hoàn chỉnh.
Điểm: 100
Bạn cần mua ~N~ món hàng trong siêu thị, món hàng thứ ~i~ có giá ban đầu là ~A_i~ đồng. Bạn đang có trong tay ~K~ phiếu giảm giá.
Mỗi phiếu giảm giá có thể được sử dụng cho một món hàng bất kỳ. Khi áp dụng 1 phiếu giảm giá lên món hàng có giá ~X~, giá của món hàng đó sẽ giảm đi một nửa (tức là giá mới sẽ bằng phần nguyên của phép chia ~X / 2~, hay ~\lfloor X / 2 \rfloor~).
Lưu ý: Bạn hoàn toàn có thể sử dụng nhiều phiếu giảm giá cho cùng một món hàng để giá giảm sâu hơn (ví dụ: áp dụng 2 phiếu cho giá 30 đồng ~\rightarrow~ giảm còn 15 đồng ~\rightarrow~ giảm tiếp còn 7 đồng).
Hãy tính tổng số tiền tối thiểu bạn phải trả để mua hết ~N~ món hàng trên.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~K~ (~1 \le N, K \le 10^5~).
- Dòng thứ hai chứa ~N~ số nguyên ~A_1, A_2, ..., A_N~ (~0 \le A_i \le 10^9~), cách nhau bởi khoảng trắng.
Kết quả
In ra một số nguyên duy nhất là tổng số tiền tối thiểu cần trả. (Kết quả có thể vượt quá giới hạn số nguyên 32-bit).
Ví dụ
Input
3 2
10 20 30
Output
35
Giải thích
Có 3 món đồ (giá 10, 20, 30) và 2 phiếu giảm giá. Cách dùng tối ưu nhất:
- Dùng 1 phiếu cho món 30, giá giảm còn 15.
- Dùng 1 phiếu cho món 20, giá giảm còn 10.
- Tổng số tiền phải trả: ~10 + 10 + 15 = 35~.
(Lưu ý: Nếu dồn cả 2 phiếu cho món 30, nó sẽ giảm còn 15, rồi giảm tiếp còn 7. Tổng tiền khi đó là ~10 + 20 + 7 = 37~, không tối ưu bằng cách trên).
Điểm: 100
Bạn nhận được một luồng dữ liệu gồm các số nguyên được truyền đến liên tục. Sau khi nhận được mỗi số mới, bạn hãy tính và in ra số trung vị (Median) của tất cả các số đã nhận được tính đến thời điểm hiện tại.
Nhắc lại về Số trung vị:
- Nếu số lượng phần tử của tập hợp là số lẻ, trung vị là phần tử đứng chính giữa khi tập hợp được sắp xếp tăng dần.
- Nếu số lượng phần tử là số chẵn, trung vị là trung bình cộng của 2 phần tử đứng chính giữa.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 10^5~) là tổng số lượng các số sẽ được truyền đến.
- ~N~ dòng tiếp theo, mỗi dòng chứa một số nguyên ~X~ (~-10^9 \le X \le 10^9~).
Kết quả
In ra ~N~ dòng, dòng thứ ~i~ là số trung vị của tập hợp sau khi nhận được ~i~ số đầu tiên. Kết quả in ra dưới dạng số thập phân với đúng 1 chữ số sau dấu phẩy.
Ví dụ
Input
4
5
15
1
3
Output
5.0
10.0
5.0
4.0
Giải thích
- Nhận
5: Tập hợp[5]. Trung vị = ~5.0~ - Nhận
15: Tập hợp[5, 15]. Trung vị = ~(5 + 15) / 2 = 10.0~ - Nhận
1: Tập hợp[1, 5, 15]. Trung vị = ~5.0~ - Nhận
3: Tập hợp[1, 3, 5, 15]. Trung vị = ~(3 + 5) / 2 = 4.0~
Điểm: 100
Một CPU cần xử lý một mảng các ký tự đại diện cho các tác vụ, mỗi tác vụ được ký hiệu bằng một chữ cái in hoa từ A đến Z. Mỗi tác vụ tốn đúng 1 đơn vị thời gian để hoàn thành.
Để hệ thống không bị quá tải, có một quy định về thời gian nghỉ (cooldown) là ~K~: Bất kỳ hai tác vụ cùng loại (cùng ký tự) nào cũng phải được xử lý cách nhau ít nhất ~K~ đơn vị thời gian. Trong khoảng thời gian chờ đó, CPU có thể xử lý các tác vụ khác loại, hoặc phải nghỉ (Idle) nếu không có tác vụ nào khả dụng.
Hãy tìm khoảng thời gian ngắn nhất để CPU hoàn thành toàn bộ mảng tác vụ này.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 10^5~) là số lượng tác vụ và số nguyên ~K~ (~0 \le K \le 100~) là thời gian cooldown.
- Dòng thứ hai chứa chuỗi ~S~ độ dài ~N~ chỉ gồm các chữ cái in hoa từ
AđếnZ.
Kết quả
In ra một số nguyên duy nhất là tổng thời gian tối thiểu (bao gồm cả các khoảng Idle) để xử lý hết chuỗi tác vụ.
Ví dụ
Input 1
6 2
AAABBB
Output 1
8
Giải thích: Lịch xử lý tối ưu là A -> B -> Idle -> A -> B -> Idle -> A -> B. Mất tổng cộng 8 đơn vị thời gian.
Input 2
6 0
AAABBB
Output 2
6
Giải thích: ~K = 0~ nên không cần thời gian nghỉ, CPU làm liên tục A->A->A->B->B->B mất 6 đơn vị thời gian.
Điểm: 100
Có ~N~ công việc khác nhau đang chờ bạn thực hiện. Công việc thứ ~i~ có thời hạn hoàn thành (deadline) là ~D_i~ và nếu hoàn thành đúng hạn, bạn sẽ nhận được mức lợi nhuận là ~P_i~.
Mỗi công việc đều tiêu tốn chính xác 1 đơn vị thời gian để hoàn thành. Bạn chỉ có thể làm một công việc tại một thời điểm, và bắt đầu công việc đầu tiên ở thời điểm ~t = 0~. Một công việc được gọi là hoàn thành đúng hạn nếu thời điểm nó hoàn thành nhỏ hơn hoặc bằng ~D_i~.
Hãy tìm cách chọn và sắp xếp các công việc sao cho tổng lợi nhuận thu được là lớn nhất có thể.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 10^5~).
- ~N~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~D_i~ và ~P_i~ (~1 \le D_i \le 10^5~, ~1 \le P_i \le 10^9~), cách nhau bởi khoảng trắng.
Kết quả
In ra một số nguyên duy nhất là tổng lợi nhuận tối đa bạn có thể thu được. (Lưu ý: Kết quả có thể vượt quá giới hạn số nguyên 32-bit).
Ví dụ
Input
5
2 100
1 19
2 27
1 25
3 15
Output
142
Giải thích
Có 5 công việc. Các công việc được chọn để thực hiện là:
- Thời gian
0 -> 1: Làm công việc 4 (Deadline = 1, Profit = 25). - Thời gian
1 -> 2: Làm công việc 1 (Deadline = 2, Profit = 100). - Thời gian
2 -> 3: Làm công việc 5 (Deadline = 3, Profit = 15). Tổng lợi nhuận: ~25 + 100 + 15 = 140~. Khoan đã, nếu bỏ công việc 5, làm công việc 3 (Profit = 27) thay vào vị trí công việc 4 thì sao? Cách tối ưu thực sự: 0 -> 1: Làm công việc 3 (Deadline = 2, Profit = 27).1 -> 2: Làm công việc 1 (Deadline = 2, Profit = 100).2 -> 3: Làm công việc 5 (Deadline = 3, Profit = 15). Tổng lợi nhuận = ~27 + 100 + 15 = 142~. (Các công việc 1 và 3 đều có deadline là 2 nên ta phải làm chúng trong 2 giờ đầu tiên).
Điểm: 100
Bạn đang xây dựng một tòa tháp bằng ~N~ viên gạch, các viên gạch có kích thước khác nhau đôi một, lần lượt từ ~1~ đến ~N~.
Quá trình giao gạch kéo dài trong đúng ~N~ ngày. Mỗi ngày, bạn sẽ nhận được chính xác 1 viên gạch. Các viên gạch nhận được tạo thành một hoán vị của các số từ ~1~ đến ~N~.
Quy tắc xây tháp: Bạn chỉ có thể đặt một viên gạch có kích thước ~X~ lên tháp nếu tất cả các viên gạch có kích thước lớn hơn nó (từ ~X+1~ cho đến ~N~) đều đã được đặt lên tháp. Nếu một viên gạch nhận được chưa thỏa mãn điều kiện để đặt lên tháp, bạn phải cất nó vào kho chứa tạm thời.
Hãy in ra kích thước của các viên gạch được đặt lên tháp trong mỗi ngày.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \le N \le 10^5~).
- Dòng thứ hai chứa ~N~ số nguyên là kích thước của các viên gạch nhận được theo thứ tự từ ngày 1 đến ngày ~N~. Dữ liệu đảm bảo đây là một hoán vị của ~1 \dots N~.
Kết quả
In ra ~N~ dòng. Dòng thứ ~i~ chứa kích thước của các viên gạch được đặt lên tháp trong ngày thứ ~i~, theo thứ tự giảm dần và cách nhau bởi một khoảng trắng. Nếu trong ngày đó không có viên gạch nào được đặt lên tháp, hãy in ra một dòng trống.
Ví dụ
Input
5
4 5 1 2 3
Output
5 4
3 2 1
Giải thích
- Ngày 1: Nhận gạch 4. Chờ gạch 5 $\rightarrow$ Cất vào kho. (In dòng trống)
- Ngày 2: Nhận gạch 5. Đặt gạch 5 lên tháp. Kiểm tra kho thấy gạch 4 cũng đã thỏa mãn điều kiện (vì 5 đã đặt) $\rightarrow$ Lấy 4 ra đặt lên tháp. (In
5 4) - Ngày 3: Nhận gạch 1. Chờ gạch 3 và 2 $\rightarrow$ Cất kho. (In dòng trống)
- Ngày 4: Nhận gạch 2. Chờ gạch 3 $\rightarrow$ Cất kho. (In dòng trống)
- Ngày 5: Nhận gạch 3. Đặt gạch 3. Sau đó lấy gạch 2 từ kho ra đặt, tiếp tục lấy gạch 1 ra đặt. (In
3 2 1)
Điểm: 100
Một người lính đánh thuê cần di chuyển qua một khu vực nguy hiểm được mô phỏng bởi một lưới chữ nhật kích thước ~N \times M~. Người lính xuất phát từ góc trên cùng bên trái ở tọa độ ~(1, 1)~ và cần đi đến điểm tập kết ở góc dưới cùng bên phải tại tọa độ ~(N, M)~.
Tại mỗi ô ~(i, j)~ trên lưới, người lính sẽ phải tiêu tốn một mức năng lượng (hoặc tiền bạc) là ~C_{i, j}~ để có thể bước vào ô đó. Từ một ô, người lính chỉ có thể di chuyển sang 4 ô kề cạnh (Lên, Xuống, Trái, Phải). Tổng chi phí của hành trình được tính bằng tổng chi phí của tất cả các ô trên đường đi (bao gồm cả ô xuất phát ~(1, 1)~ và ô đích ~(N, M)~).
Hãy tìm một đường đi sao cho tổng chi phí (năng lượng) tiêu tốn là nhỏ nhất.
Gợi ý: Thuật toán BFS thông thường bằng Queue chỉ đúng khi chi phí ở mọi ô bằng nhau. Với chi phí khác nhau, hãy sử dụng Thuật toán Dijkstra kết hợp Hàng đợi ưu tiên nhỏ nhất (Min-Heap).
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên dương ~N~ và ~M~ (~1 \le N, M \le 500~).
- ~N~ dòng tiếp theo, mỗi dòng chứa ~M~ số nguyên không âm ~C_{i, j}~ (~0 \le C_{i, j} \le 10^5~) thể hiện chi phí bước vào ô ~(i, j)~. Hai số liên tiếp cách nhau một khoảng trắng.
Kết quả
In ra một số nguyên duy nhất là tổng chi phí nhỏ nhất để đi từ ~(1, 1)~ đến ~(N, M)~.
Ví dụ
Input
3 3
1 3 1
1 5 1
4 2 1
Output
7
Giải thích
Thay vì đi đường chéo xuống (chi phí ~1 + 5 + 1 = 7~ nhưng không được đi chéo) hoặc đi theo rìa trái-dưới (chi phí ~1 + 1 + 4 + 2 + 1 = 9~), người lính chọn đi theo đường vòng sang phải: ~(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)~. Tổng chi phí tương ứng: ~1 + 3 + 1 + 1 + 1 = 7~.