Kho báu 2
Đề bài
Có một ngôi làng ở vùng đất xa xôi, người dân đã tìm được kho báu với nhiều trang sức. Để chia kho báu cho người dân trong làng, người ta đưa ra một số quy định cho mỗi dân khi vào được kho báu để lấy trang sức.
Trong kho báu có $N$ món đồ trang sức, mỗi món đồ có khối lượng $M[i]$ và giá trị $V[i]$. Mike có $K$ túi để đựng chiến lợi phẩm của mình, và mỗi túi có thể chứa khối lượng tối đa là $C[i]$. Anh ta dự định cất giữ tất cả chiến lợi phẩm của mình vào những chiếc túi này, nhưng tối đa một món đồ trang sức trong mỗi túi, để giảm khả năng bị hư hại trong quá trình di chuyển ra khỏi kho báu.
Yêu cầu: tìm giá trị trang sức tổng cộng tối đa mà Mike có thể "lấy được".
Dữ liệu:
- Dòng đầu tiên chứa hai số $N$ và $K$ $(1 \le N, K \le 3 \cdot 10^5)$.
- Mỗi dòng trong số $N$ dòng tiếp theo chứa một cặp số $M[i]$ và $V[i]$ $(1 \le M[i], V[i] \le 10^6)$.
- Mỗi dòng trong số $K$ dòng tiếp theo chứa một số $C[i]$ $(1 \le C[i] \le 10^9)$.
- Tất cả các số trong đầu vào là số nguyên dương.
Kết quả: dòng đầu tiên và duy nhất của đầu ra phải chứa giá trị trang sức tổng cộng tối đa có thể.
Ràng buộc: $N, K < 5000$ chiếm 50% số điểm; số điểm còn lại không ràng buộc gì thêm.
2 1
5 10
100 100
11103 2
1 65
5 23
2 99
10
2164Giải thích ví dụ 1: có 1 túi chỉ chứa được món có khối lượng $\le 11$. Món 1 (khối lượng 5) chứa được, món 2 (khối lượng 100 > 11) thì không. Chỉ có món 1 khả thi nên lấy món 1, giá trị $10$.
Giải thích ví dụ 2: túi 1 sức chứa 10, túi 2 sức chứa 2. Túi sức chứa 2 lấy món giá trị 99 (khối lượng 2), túi sức chứa 10 lấy món giá trị 65 (khối lượng 1) → tổng $99 + 65 = 164$.
int → biến đáp án phải là long long. Trong bộ test có 35 test đáp án vượt $2^{31} - 1$.Lời mở đầu
Bài này là phiên bản "mỗi túi một món" của bài cái túi, và nhờ ràng buộc đó mà nó trở thành một bài tham lam rất đẹp (bài gốc là "Jewel Thief" nổi tiếng). Mình sẽ đi từ cách tham lam trực tiếp $O(N \cdot K)$ ăn 50% điểm, rồi tăng tốc bằng hàng đợi ưu tiên (priority_queue) để được $O((N + K) \log N)$.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJLộ trình lời giải, bấm vào từng phần để nhảy tới:
Bộ testBộ test chính thức có gì?
Bộ test có 100 test, khớp với ràng buộc của đề:
| Test | N | K | M, V | C | Đáp án |
|---|---|---|---|---|---|
| 1 – 20 | 5 … 10 | 1 … 8 | ≤ 20 | 1 … 25 | 7 … 104 |
| 21 – 50 | 4 999 … 4 999 | 213 … 4 190 | ≤ 999 994 | 1 … 999 893 597 | 190 065 984 … 535 146 353 |
| 51 – 100 | 300 000 … 300 000 | 244 … 243 090 | ≤ 999 999 | 1 … 999 997 732 | 243 468 164 … 30 679 278 407 |
- Test 1 – 20: rất nhỏ ($N \le 10$, các số $\le 25$), có test chỉ 1 túi.
- Test 21 – 50: $N = 4999$, $K$ từ 213 tới 4190 – vừa đúng dưới ngưỡng 5000 của subtask 1.
- Test 51 – 100: $N = 3 \cdot 10^5$, $K$ thay đổi từ 244 tới 243 090; 35 test có đáp án vượt $2^{31} - 1$ (lớn nhất $\approx 3.07 \cdot 10^{10}$).
- Mọi test từ 21 trở đi đều có túi sức chứa 1 – túi này chỉ đựng được món nặng đúng 1.
Bảng subtask:
| Subtask | Điều kiện | Test | Cách 1 | Cách 2 |
|---|---|---|---|---|
| 1 (50%) | $N, K < 5000$ | 1 – 50 | ✔ | ✔ |
| 2 (50%) | $N = 3 \cdot 10^5$ | 51 – 100 | ✘ (chỉ qua vài test K nhỏ) | ✔ |
Ý tưởngTúi nhỏ chọn trước, lấy món đắt nhất
Mỗi túi chứa tối đa 1 món nên bài toán là ghép túi với món. Túi nhỏ thì "kén chọn" (chỉ chứa được ít món), túi lớn thì dễ tính. Vậy hãy xét túi theo sức chứa tăng dần:
Vì sao đúng? Gọi túi nhỏ nhất là $c$, món đắt nhất vừa nó là $x$. Xét một cách ghép tối ưu bất kỳ. Nếu $x$ không được lấy, cho túi $c$ đựng $x$ thay cho món cũ (nếu có): tổng không giảm vì $x$ đắt nhất trong các món vừa $c$. Nếu $x$ đang nằm ở túi $c' \ge c$ khác, đổi chỗ món của túi $c$ (món này nhẹ hơn $c \le c'$ nên vừa túi $c'$) với $x$: tổng không đổi. Vậy luôn có cách tối ưu mà túi $c$ đựng $x$ – lặp lại với các túi còn lại.
Chú ý quan trọng để tăng tốc: món nào đã vừa túi $c$ thì cũng vừa mọi túi sau (to hơn). Nên nếu sắp xếp món theo khối lượng tăng dần, khi chuyển sang túi to hơn ta chỉ việc thêm các món mới vừa vào một "kho các món có thể lấy", rồi rút món đắt nhất ra – đúng là việc của một hàng đợi ưu tiên.
Em nhập các món (cặp khối_lượng giá_trị, cách nhau dấu phẩy) và các túi rồi bấm Tiếp:
Cách 1Tham lam trực tiếp O(N·K) – ăn subtask 1
Cài đặt thẳng ý tưởng: sắp xếp túi tăng dần, với mỗi túi duyệt lại toàn bộ $N$ món để tìm món đắt nhất chưa dùng mà vừa túi, đánh dấu used.
Kết quả chạy thật: bản C++ đúng 54/100 test: trọn subtask 1 (test 1 – 50, $N \cdot K \le 2 \cdot 10^7$) và thêm 4 test lớn có $K$ chỉ vài trăm túi; các test lớn còn lại ($N \cdot K$ lên tới $7 \cdot 10^{10}$) quá thời gian. Bản Python chỉ đúng 35/100: ngay cả trong subtask 1, các test có $K$ vài nghìn đã quá 1 giây.
Cách 2Sắp xếp + hàng đợi ưu tiên – đủ điểm
Sắp xếp món theo khối lượng, túi theo sức chứa. Con trỏ p chạy trên dãy món: với túi c[j], đẩy mọi món có khối lượng $\le$ c[j] vào pq (heap lớn nhất theo giá trị), rồi lấy phần tử đỉnh. Mỗi món vào heap và ra heap tối đa 1 lần, con trỏ p chỉ tiến không lùi – giống hệt kỹ thuật hai con trỏ.
priority_queue<int>mặc định là heap lớn nhất:top()trả về giá trị lớn nhất.- Các món còn lại trong heap sau khi lấy vẫn vừa các túi sau nên không cần xoá.
- Bản Python dùng
heapq(heap nhỏ nhất) nên lưu-giá_trị.
Kết quả chạy thật: bản C++ đúng 100/100 test, test chậm nhất (test 52) chạy 0.16 giây. Bản Python đúng 50/100: thuật toán giống hệt nhưng với $N = 3 \cdot 10^5$ thì việc đọc dữ liệu, sắp xếp và thao tác heapq trong Python vượt 1 giây.
long long.
Nhận xét
Đăng nhận xét