Thành sĩ gái
Đề bài
Nhân dịp chào đón Giáng sinh, Thành quyết định lấy hết tiền học bổng của mình để mua toàn bộ $N$ món quà lưu niệm tặng các bạn nữ trong lớp, các món quà được đánh số từ $1$ đến $N$, món thứ $i$ có giá là $a_i$ $(i = 1 \div N)$. Cảm động trước hành động của Thành, chủ cửa hàng đã có chương trình khuyến mãi đặc biệt dành cho em. Thành được phép chia $N$ món quà thành một hay nhiều đơn hàng với điều kiện hai món quà bất kì trong một đơn phải có giá chênh lệch nhau không bé hơn $K$. Với mỗi đơn hàng như vậy, Thành chỉ phải thanh toán số tiền là giá của món quà đắt nhất trong đơn đó mà thôi.
Yêu cầu: Giúp Thành chia $N$ món quà thành các đơn hàng sao cho tổng số tiền phải trả cho tất cả đơn hàng là nhỏ nhất.
Dữ liệu: vào gồm 2 dòng:
- Dòng thứ nhất chứa hai số nguyên dương $N$ và $K$ $(N \le 10^5,\ K \le 10^9)$.
- Dòng thứ hai gồm $N$ số nguyên dương $a_1, a_2, \ldots, a_N$ $(a_i \le 10^9$ với mọi $i = 1 \div N)$.
Kết quả: ghi ra một số nguyên duy nhất là tổng số tiền phải trả.
Ràng buộc:
- Có 50% số test ứng với 50% số điểm có $N \le 10^4$;
- Có 50% số test còn lại ứng với 50% số điểm không có ràng buộc gì thêm.
3 2
1 3 36Giải thích ví dụ: chia thành 2 đơn $\{3, 1\}$ (chênh lệch $2 \ge K$, trả $3$) và $\{3\}$ (trả $3$), tổng $6$. Hai món giá $3$ không thể chung một đơn vì chênh lệch $0 < 2$.
Lời mở đầu
Một bài tham lam rất đẹp: đọc đề tưởng phải thử mọi cách chia đơn (số cách chia là khổng lồ), nhưng chỉ cần xét các món từ đắt đến rẻ là mọi thứ trở nên rõ ràng. Phần cài đặt là chỗ để luyện multiset và hàm lower_bound – đúng chủ đề Map/Set. Cuối bài mình còn chỉ ra một nhận xét giúp bỏ luôn multiset, chỉ cần hai con trỏ.
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 OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ 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ì?
| Test | N | K | Giá lớn nhất | Đáp án lớn nhất |
|---|---|---|---|---|
| 1 – 10 | 4 … 10 | 1 … 10 | 10 | 57 |
| 11 – 50 | 10.000 | 3 … 935.507.608 | 999.979.820 | 692.919.719.871 |
| 51 – 100 | 100.000 | 1 … 393.464.216 | 999.999.855 | 4.575.304.827.212 |
- Bộ test có 100 test: 10 test đầu rất nhỏ ($N \le 10$, dùng để kiểm tra tính đúng), 40 test $N = 10^4$ và 50 test $N = 10^5$.
- $K$ trải rộng từ $1$ tới hàng trăm triệu – $K$ càng lớn thì càng khó ghép, số đơn hàng càng nhiều (đây chính là điểm yếu của Cách 1).
- Đáp án lớn tới 4.575.304.827.212, có 58 test vượt quá kiểu
int→ tổng tiền bắt buộc dùnglong long. - Giá các món có rất nhiều giá trị trùng nhau (ví dụ test $N = 10^5$ chỉ có khoảng 62 nghìn giá khác nhau) → phải dùng
multisetchứ không phảiset.
Hai subtask khớp đúng với bộ test như sau (ô ghi số test đúng của từng cách – chạy thật):
| Subtask | Điều kiện | Các test | Cách 1 O(N·số đơn) | Cách 2 multiset | Cách 3 hai con trỏ |
|---|---|---|---|---|---|
| 1 (50%) | $N \le 10^4$ | 1 – 50 | 50/50 | 50/50 | 50/50 |
| 2 (50%) | $N \le 10^5$ | 51 – 100 | 36/50 | 50/50 | 50/50 |
Ý tưởngXét từ món đắt nhất, ghép được thì ghép
Nhận xét 1. Nếu xếp các món trong một đơn theo giá giảm dần $x_1 \ge x_2 \ge \ldots \ge x_m$, thì điều kiện "hai món bất kì chênh lệch $\ge K$" tương đương với hai món liền nhau chênh lệch $\ge K$ (vì $x_1 - x_3$ $= (x_1 - x_2) + (x_2 - x_3)$ $\ge 2K$ $\ge K$...). Vậy mỗi đơn là một "chuỗi" đi xuống, mỗi bước giảm ít nhất $K$, và Thành trả tiền món đầu chuỗi.
Nhận xét 2. Sắp xếp các món giảm dần rồi xét lần lượt. Khi tới món $x$, mọi món đã xét đều $\ge x$, nên $x$ chỉ có hai lựa chọn:
- Ghép vào cuối một đơn cũ có món rẻ nhất (gọi là đuôi) $\ge x + K$ → miễn phí, đuôi của đơn đó trở thành $x$.
- Mở đơn mới → $x$ là món đắt nhất của đơn mới (các món sau đều rẻ hơn), phải trả $x$.
Vì sao "ghép được thì ghép" không bao giờ thiệt? So sánh hai lựa chọn khi có đơn với đuôi $v \ge x + K$: ghép thì tập đuôi là "bỏ $v$, thêm $x$", không mất tiền; mở mới thì tập đuôi là "thêm $x$" nhưng mất $x$ đồng. Lựa chọn mở mới chỉ "lời" ở chỗ còn giữ đuôi $v$ – nhưng đuôi đó chỉ giúp ghép miễn phí một món $y$ sau này, mà $y \le x$, tức là tiết kiệm được tối đa $y \le x$, không bù nổi $x$ đồng đã trả. Vậy ghép luôn có lợi hơn hoặc bằng.
Ghép vào đơn nào? Đơn nào có đuôi $\ge x + K$ cũng được – vì các món $y$ xét sau đều $\le x$, nên mọi đuôi $\ge x + K$ cũng đều $\ge y + K$, "tốt như nhau" với các món sau. Cách 2 dùng lower_bound lấy đuôi nhỏ nhất thoả mãn cho tự nhiên; Cách 3 khai thác chính nhận xét này để bỏ hẳn multiset.
Em nhập $K$ và giá các món rồi bấm Tiếp để xem từng món được ghép vào đơn nào (ô vàng là món phải trả tiền – đầu mỗi đơn, ô viền cam là đuôi của đơn):
Cách 1Duyệt từng đơn để tìm chỗ ghép – O(N · số đơn)
Cài đặt thẳng ý tưởng: lưu đuôi của các đơn trong một vector cuoi. Với mỗi món, duyệt lần lượt các đơn, gặp đơn đầu tiên có đuôi $\ge a_i + K$ thì ghép vào.
sort(a.rbegin(), a.rend())sắp xếp giảm dần (duyệt mảng theo chiều ngược rồi sắp tăng).chon = -1nghĩa là "chưa tìm được đơn nào"; tìm được thìbreakngay.- Như đã nói ở phần ý tưởng, chọn đơn đầu tiên thoả mãn vẫn đúng, không cần chọn đơn "đẹp nhất".
Kết quả chạy thật: bản C++ đúng 86/100 test (quá 1 giây ở các test 53, 56, 61, 64–65, 67–69, 73, 77–78, 80, 84, 96), test đúng chạy lâu nhất 0.922s; bản Python đúng 28/100 test (quá thời gian ở các test 12–15, 18–20, 25, 29–31, 33–34, 37–38, 41–46, 48, 50–54, 56–100), lâu nhất 0.85s.
Điều thú vị: Cách 1 không chỉ qua subtask 1 mà còn qua kha khá test của subtask 2. Lý do là thời gian phụ thuộc vào số đơn hàng: $K$ nhỏ thì hầu như món nào cũng ghép được ngay vào đơn đầu tiên, vòng for j chạy rất ít. Các test bị quá thời gian đều có $K$ lớn (từ vài trăm nghìn trở lên) – khi đó có hàng chục nghìn đơn và mỗi món phải duyệt qua chừng ấy đơn.
Cách 2multiset + lower_bound – O(N log N)
Thay vì duyệt từng đơn, ta cất các đuôi vào một multiset (tự sắp tăng dần, cho phép trùng). Câu hỏi "có đuôi nào $\ge a_i + K$ không" chính là lower_bound(a[i] + k): trả về đuôi nhỏ nhất mà $\ge a_i + K$, hoặc end() nếu không có.
- Dù ghép hay mở đơn mới thì $a_i$ đều trở thành đuôi của một đơn, nên
cuoi.insert(a[i])nằm ngoàiif. Ghép thì xoá đuôi cũcuoi.erase(it)trước. erase(it)xoá đúng một phần tử tại vị tríit. Nếu viếtcuoi.erase(*it)(xoá theo giá trị) thì multiset xoá tất cả các phần tử bằng giá trị đó – sai!- Bản Python không có multiset nên mình dùng
heapqlấy đuôi lớn nhất: nếu đuôi lớn nhất cũng không đủ $\ge x + K$ thì không đơn nào nhận được. Theo nhận xét ở phần ý tưởng, ghép vào đuôi lớn nhất cũng đúng.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.040s; bản Python đúng 100/100 test, lâu nhất 0.13s.
Cách 3Bỏ luôn multiset: hai con trỏ – O(N log N) cho sắp xếp
Vì ghép vào đuôi nào cũng được, ta chọn đuôi lớn nhất. Hãy để ý: các đuôi được thêm vào theo thứ tự giảm dần (vì các món được xét giảm dần) → đuôi lớn nhất luôn là đuôi được thêm vào sớm nhất còn lại. Tập đuôi hoạt động đúng như một hàng đợi: thêm ở cuối, lấy ra ở đầu!
Món nào cũng thành đuôi đúng một lần, nên hàng đợi chính là mảng a đã sắp xếp, đầu hàng đợi là một con trỏ j: các món $a_j, a_{j+1}, \ldots, a_{i-1}$ là các đuôi hiện có, lớn nhất là $a_j$.
- Nếu $a_j \ge a_i + K$: ghép $a_i$ sau $a_j$ → $a_j$ không còn là đuôi nữa (
j++), còn $a_i$ thành đuôi mới (tự động vì nó nằm ở cuối "hàng đợi"). - Không cần kiểm tra
j < i: khij == ithì điều kiện thành $a_i \ge a_i + K$, sai vì $K \ge 1$.
Kết quả chạy thật: bản C++ đúng 100/100 test, test đúng chạy lâu nhất 0.022s; bản Python đúng 100/100 test, lâu nhất 0.09s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất (test đúng) | Ghi chú |
|---|---|---|---|---|
| 1. Duyệt từng đơn | C++ | 86/100 | 0.922s | Quá thời gian ở test 53, 56, 61, 64–65, 67–69, 73, 77–78, 80, 84, 96 |
| Python | 28/100 | 0.847s | Quá thời gian ở test 12–15, 18–20, 25, 29–31, 33–34, 37–38, 41–46, 48, 50–54, 56–100 | |
| 2. multiset | C++ | 100/100 | 0.040s | Full điểm |
| Python (heapq) | 100/100 | 0.134s | Full điểm | |
| 3. Hai con trỏ | C++ | 100/100 | 0.022s | Full điểm |
| Python | 100/100 | 0.094s | Full điểm |
long long cho tổng tiền. Bài học rút ra: khi gặp bài "chia nhóm" với chi phí là phần tử lớn nhất, hãy thử sắp xếp rồi xét từ lớn đến nhỏ.
Nhận xét
Đăng nhận xét