Vận chuyển hàng
Đề bài
Có $N$ kho hàng, các kho hàng chứa các thùng hàng cùng loại. Chủ các kho hàng này muốn chuyển tất cả các thùng hàng về một kho nào đó trong $N$ kho nói trên, vì vậy ông ta khoán công việc này cho một nhóm công nhân bốc vác. Khi hợp đồng, các công nhân và ông chủ kho hàng thống nhất công để chuyển một kho hàng này về kho kia là một thùng hàng.
Yêu cầu: giúp ông chủ xác định số thùng hàng ít nhất dùng để trả công cho nhóm công nhân để chuyển tất cả các thùng hàng về một kho.
Dữ liệu vào: từ file BAI1.INP có cấu trúc như sau:
- Dòng đầu ghi số $N$ là số kho hàng $(N \le 10^5)$.
- Dòng thứ hai ghi $N$ số nguyên dương $a_1, a_2, \ldots, a_N$ $(1 < a_i \le 10^3)$, trong đó $a_i$ là số thùng hàng có trong kho thứ $i$ $(1 \le i \le N)$.
Kết quả: ghi ra file BAI1.OUT gồm một số là số thùng hàng dùng để trả công.
5
2 6 5 8 23BAI1.INP / BAI1.OUT. Code bên dưới dùng if (fopen("BAI1.INP", "r")) { freopen(...); }: có file thì đọc file, không có file thì đọc bàn phím – nộp kiểu nào cũng chạy.Lời mở đầu
Bài này là câu 1 của đề khảo sát HSG Thanh Hoá. Đề rất ngắn, code cũng rất ngắn, nhưng nếu đọc vội thì em sẽ nghĩ ngay: "có $N$ kho, gom về 1 kho thì phải chuyển $N - 1$ lần, trả $N - 1$ thùng" – và ví dụ đã báo sai ngay: $N = 5$ mà đáp án là 3 chứ không phải 4. Cái hay của bài nằm ở chỗ hiểu cho đúng thùng trả công lấy từ đâu. Hiểu đúng rồi thì lời giải là một phép tham lam rất đẹp.
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ông ghi subtask, nhưng bộ test chia rõ thành 3 mức kích thước:
| Test | Số test | N | aᵢ | Đáp án | Tiết kiệm so với N − 1 |
|---|---|---|---|---|---|
| 1 – 30 | 30 | 3 … 9 | 2 … 10 | 2 … 7 | 0 … 2 |
| 31 – 60 | 30 | 10 000 … 10 000 | 2 … 999 | 7 991 … 8 061 | 1 938 … 2 008 |
| 61 – 100 | 40 | 100 000 … 100 000 | 2 … 999 | 80 182 … 80 397 | 19 602 … 19 817 |
- Test 1 – 30: rất nhỏ, $3 \le N \le 9$, $2 \le a_i \le 10$. Có 11 test không tiết kiệm được thùng nào (đáp án đúng bằng $N - 1$) – ví dụ khi các kho đều khá lớn so với $N$.
- Test 31 – 100: $N = 10^4$ hoặc $10^5$, $a_i$ trải từ 2 tới 999, khoảng 31% số kho chỉ có 2 – 9 thùng. Nhờ đem các kho nhỏ trả công mà tiết kiệm được gần 20% số lần chuyển.
- Ví dụ của đề (
2 6 5 8 2) không nằm trong bộ test. Đáp án lớn nhất cỡ $8 \cdot 10^4$ nên dùngintthoải mái.
Mình tạm chia 3 mức thành 3 "subtask" để so sánh các cách giải:
| Subtask | Điều kiện | Test | Cách ăn được |
|---|---|---|---|
| 1 | N ≤ 9 | 1 – 30 | Cách 1, 2, 3 |
| 2 | N = 10⁴ | 31 – 60 | Cách 2, 3 |
| 3 | N = 10⁵ | 61 – 100 | Cách 3 |
Ý tưởngKho đem trả công hết thì khỏi phải chuyển
Thùng hàng dùng để trả công thì cũng phải lấy từ các kho. Mấu chốt là:
Xem ví dụ 2 6 5 8 2: lấy cả 2 thùng của kho 1 đem trả công, kho 1 trống. Còn 4 kho $6, 5, 8, 2$ cần gom về kho có 8 thùng: 3 lần chuyển, trả 3 thùng – trong đó 2 thùng là của kho 1 vừa rồi, thêm 1 thùng lấy ở kho nào cũng được. Tổng cộng 3 thùng, đúng đáp án!
Tổng quát, gọi $S$ là tập các kho đem trả công hết, $|S| = k$ và tổng số thùng của chúng là $T$:
- Còn $N - k$ kho phải gom về một kho → cần $N - 1 - k$ lần chuyển, tức phải trả $N - 1 - k$ thùng.
- Nhưng toàn bộ $T$ thùng của tập $S$ đã nằm trong tay công nhân rồi. Nếu $T \ge N - 1 - k$ thì ông chủ đã trả dư, tốn đúng $T$ thùng; còn nếu $T < N - 1 - k$ thì lấy thêm cho đủ từ các kho khác, tốn $N - 1 - k$ thùng.
Mình đã kiểm tra cách hiểu này trên cả 100 test của bộ test chính thức: khớp hết. Bây giờ là phần tham lam: với cùng số kho $k$, phần $N - 1 - k$ không đổi, nên ta muốn $T$ càng nhỏ càng tốt → chọn $k$ kho có ít thùng nhất. Vậy chỉ cần sắp xếp tăng dần, thử $k = 0, 1, 2, \ldots$ với $T_k = a_1 + a_2 + \cdots + a_k$ (tổng $k$ số nhỏ nhất):
- $N - 1 - k$ giảm dần khi $k$ tăng, còn $T_k$ tăng dần. Đáp án là $\min_k \max(N - 1 - k, T_k)$ – chỗ hai đường "gặp nhau".
- Khi $T_k$ đã vượt đáp án tốt nhất hiện có thì dừng được, vì $T$ chỉ tăng thêm.
Em nhập số thùng các kho rồi bấm Tiếp để xem từng kho nhỏ được đem trả công. Ô vàng là kho trả công hết (khỏi chuyển), ô xanh là kho đích:
Cách 1Vét cạn mọi tập kho trả công – O(2ᴺ · N)
Chưa nghĩ ra tham lam thì cứ thử hết: mỗi tập con $S$ ứng với một số mask từ $0$ tới $2^N - 1$ (bit $i$ bằng 1 nghĩa là kho $i$ được đem trả công). Bỏ tập rỗng (đã tính sẵn là $N - 1$) và tập đầy đủ (không còn kho nào để chứa hàng).
mask >> i & 1lấy bit thứ $i$ củamask: bằng 1 thì kho $i$ thuộc tập $S$, cộng vàokvàtong.- Mình dùng
1LL << min(n, 62)để không bị tràn số khi $n$ lớn – dù sao với $n$ lớn thì cách này cũng không chạy kịp.
Kết quả chạy thật: C++ đúng 30/100 test (test 1–30, chậm nhất 0.006 giây); test 31–100 bị quá thời gian. Python đúng 30/100 test (test 1–30, chậm nhất 0.030 giây); test 31–100 bị quá thời gian. Đúng như dự đoán: chỉ ăn được nhóm test nhỏ ($N \le 9$).
Cách 2Tham lam, mỗi lần tìm kho nhỏ nhất – O(N · k)
Dùng nhận xét tham lam: lần lượt lấy kho nhỏ nhất chưa dùng đem trả công. Chưa biết sắp xếp thì cứ mỗi lần duyệt cả mảng để tìm kho nhỏ nhất (giống sắp xếp chọn).
- Mảng
dung[]đánh dấu kho đã đem trả công để lần sau không chọn lại. - Dòng
if(tong > best) break;rất quan trọng: không có nó thì vòng ngoài chạy đủ $N - 1$ lần, độ phức tạp thành $O(N^2)$. Có nó thì chỉ chạy khoảng $k \approx N / 5$ lần (vì mỗi kho có ít nhất 2 thùng, $T_k \ge 2k$ nên $k$ không thể quá $N / 3$).
Kết quả chạy thật: C++ đúng 60/100 test (test 1–60, chậm nhất 0.035 giây); test 61–100 bị quá thời gian. Python đúng 30/100 test (test 1–30, chậm nhất 0.028 giây); test 31–100 bị quá thời gian. Với $N = 10^5$, $k$ khoảng $2 \cdot 10^4$ lần × $10^5$ phép so sánh $= 2 \cdot 10^9$ – quá chậm.
Cách 3Sắp xếp + cộng dồn – O(N log N)
Sắp xếp tăng dần một lần là xong việc "tìm kho nhỏ nhất": kho nhỏ thứ $k$ chính là a[k - 1]. Cộng dồn tong và cập nhật đáp án.
sort(a, a + n)tốn $O(N \log N)$, phần còn lại chỉ là một vòng lặp $O(N)$.- Kho đích là kho lớn nhất – luôn nằm cuối mảng nên không bao giờ bị lấy trả công ($k \le N - 1$).
- Đáp án không vượt $N - 1 < 10^5$ và nhờ
breaknêntongkhông vượt $10^5 + 10^3$ – kiểuintlà đủ.
Kết quả chạy thật: C++ đúng 100/100 test, test chậm nhất chỉ 0.021 giây. Python đúng 100/100 test, test chậm nhất chỉ 0.071 giây.
Mẹo thêm: vì $a_i \le 1000$ nên có thể thay sort bằng đếm phân phối (đếm số kho có $v$ thùng, rồi duyệt $v = 2, 3, \ldots$) để được $O(N + 1000)$. Với $N = 10^5$ thì sort đã đủ nhanh nên mình giữ code đơn giản.
Nhận xét
Đăng nhận xét