Đốn củi 2
Đề bài
Tèo là một cậu bé rất khỏe nhưng cũng cực kỳ lười biếng. Hôm nay, Tèo được phú ông giao cho nhiệm vụ vào rừng đốn củi.
Phú ông đưa cho Tèo một danh sách gồm $n$ cây của phú ông muốn đốn. Mỗi cây khi đốn sẽ mang lại cho Tèo $a_i$ bó củi. Những cây nào không đốn thì không được bó củi nào. Nếu Tèo đốn được ít nhất một nửa tổng số bó củi theo yêu cầu trong buổi sáng, thì sẽ được phú ông thưởng cho một bữa cơm trưa no nê.
Ví dụ, nếu có 3 cây trong danh sách, tương ứng cho 1, 3 và 4 bó củi, thì tổng số là 8 bó, và chỉ cần đốn đủ 4 bó là đủ điều kiện để được thưởng.
Tèo rất khỏe mạnh, có thể đốn bất kỳ cây nào mà không gặp khó khăn. Nhưng cậu lại rất lười, nên muốn đốn ít cây nhất có thể để vẫn được bữa cơm trưa ngon lành.
Tèo chỉ muốn đốn liền mạch một đoạn cây nào đó trong danh sách. Tức là Tèo chọn một cây số hiệu $k$, rồi lần lượt đốn các cây số $k, k+1, k+2, \ldots$ cho đến khi vừa đủ số bó củi tối thiểu theo yêu cầu. Tuy nhiên, để giảm bớt công sức, Tèo có thể chọn bỏ qua nhiều nhất một cây trong đoạn đó, nếu việc bỏ cây đó giúp giảm số lượng cây phải đốn mà vẫn đảm bảo đủ chỉ tiêu.
Yêu cầu: hãy xác định số lượng cây ít nhất mà Tèo cần đốn (theo chiến lược lười biếng của mình) để được phần thưởng từ phú ông.
Dữ liệu:
- Dòng thứ nhất là số nguyên $n$ $(1 \le n \le 2 \cdot 10^6)$.
- Dòng tiếp theo ghi các số nguyên $a_i$ là số bó củi khi đốn được cây thứ $i$ $(1 \le a_i \le 10^9)$.
Kết quả: Một dòng ghi số cây ít nhất mà Tèo cần phải đốn để đạt chỉ tiêu của Phú ông.
Giới hạn:
- 50% số test đầu tiên có $n \le 10^4$.
- 35% số test tiếp theo có $n \le 10^5$.
- 10% số test tiếp theo có $n \le 10^6$.
- 5% số test còn lại không có giới hạn gì thêm.
5
1 1 2 1 223
2 3 11Giải thích: ở ví dụ 1, tổng là $7$ bó nên Tèo cần ít nhất $3{,}5$, tức $4$ bó. Tèo chọn đoạn cây $3, 4, 5$ (được $2 + 1 + 2$ bó) và bỏ qua cây số 4: chỉ đốn 2 cây mà được $2 + 2 = 4$ bó. Không có cây nào một mình đủ 4 bó nên đáp án là $2$. Ở ví dụ 2, tổng là $6$ bó, riêng cây thứ 2 đã có $3$ bó – vừa đủ một nửa, đáp án là $1$.
Lời mở đầu
Đây là một bài 5 điểm, khó thật sự của phần Map/Set. Đọc đề thì tưởng chỉ là "tìm đoạn con ngắn nhất có tổng đủ lớn" quen thuộc, nhưng cái quyền được bỏ qua một cây làm bài khó lên hẳn: ta phải biết cây nhỏ nhất trong đoạn đang xét, trong khi đoạn đó liên tục được mở rộng bên phải và thu hẹp bên trái. Với $n$ lên tới $2 \cdot 10^6$, chỉ có thuật toán gần như tuyến tính mới sống sót. Mình sẽ đi từ vét cạn tới hai con trỏ + multiset (đúng tinh thần chương Map/Set) và cuối cùng là hàng đợi đơn điệu để lấy trọn 100 test.
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ì?
Bộ test có 100 test (mỗi test 1% số điểm), $n$ tăng dần theo từng nhóm:
| Test | Số test | n | a_i | T lớn nhất | Đáp án |
|---|---|---|---|---|---|
| 1 – 20 | 20 | 3 | 1 … 10 | 57 | 1 … 4 |
| 21 – 30 | 10 | 100 | 1 … 999 122 638 | 8 488 487 704 | 9 … 39 |
| 31 – 40 | 10 | 1 000 | 1 … 999 740 877 | 74 417 406 640 | 402 … 482 |
| 41 – 50 | 10 | 10 000 | 1 … 999 948 089 | 713 963 027 952 | 4 578 … 4 901 |
| 51 – 85 | 35 | 100 000 | 1 … 999 998 509 | 6 911 254 530 516 | 48 446 … 49 868 |
| 86 – 95 | 10 | 1 000 000 | 1 … 999 999 805 | 68 174 979 521 983 | 495 281 … 499 051 |
| 96 – 100 | 5 | 2 000 000 | 1 … 999 999 612 | 136 219 438 194 089 | 993 812 … 997 639 |
- 20 test đầu là test tay rất nhỏ ($n \le 10$, $a_i \le 10$), có cả 2 ví dụ của đề.
- Từ test 21 trở đi $a_i$ là số ngẫu nhiên tới gần $10^9$, tổng $T$ lên tới khoảng $1{,}4 \cdot 10^{14}$ → bắt buộc
long long. - Với dãy ngẫu nhiên lớn, đáp án xấp xỉ $n/2$: đoạn tối ưu rất dài. Vì vậy mẹo "dừng sớm khi đoạn đã dài hơn đáp án" ở cách 2 không cứu được, và mọi thuật toán phải xử lý đoạn rất dài thật nhanh.
- Test lớn nhất có $n = 2 \cdot 10^6$ số (file khoảng 20 MB) – riêng việc đọc dữ liệu đã đáng kể.
| Mức | n | Test | Cách 1 O(n³) | Cách 2 O(n²) | Cách 3 multiset | Cách 4 deque |
|---|---|---|---|---|---|---|
| 1 (20%) | ≤ 10 | 1 – 20 | ✔ | ✔ | ✔ | ✔ |
| 2 (10%) | 100 | 21 – 30 | ✔ | ✔ | ✔ | ✔ |
| 3 (10%) | 1 000 | 31 – 40 | ✔ | ✔ | ✔ | ✔ |
| 4 (10%) | 10 000 | 41 – 50 | ✘ | ✔ | ✔ | ✔ |
| 5 (35%) | 100 000 | 51 – 85 | ✘ | ✘ | ✔ | ✔ |
| 6 (10%) | 1 000 000 | 86 – 95 | ✘ | ✘ | ✘ | ✔ |
| 7 (5%) | 2 000 000 | 96 – 100 | ✘ | ✘ | ✘ | ✔ |
Phân tíchĐọc hiểu đề cho thật đúng
Gọi $T = a_1 + a_2 + \cdots + a_n$. "Ít nhất một nửa" nghĩa là số bó đốn được $S$ phải thoả $S \ge \frac{T}{2}$. Để khỏi dính tới số thực (vì $T$ có thể lẻ), ta viết thành:
Tèo chọn một đoạn liên tiếp $[l, r]$, có 2 lựa chọn:
- Đốn hết: đốn $r - l + 1$ cây, được $S = a_l + \cdots + a_r$ bó.
- Bỏ qua 1 cây: đốn $r - l$ cây. Bỏ cây nào thì số cây đốn vẫn như nhau, nên khôn ngoan nhất là bỏ cây ít củi nhất trong đoạn, được $S - \min(a_l..a_r)$ bó. (Đoạn phải có ít nhất 2 cây thì mới bỏ qua được.)
Đáp án là số cây đốn ít nhất trong mọi đoạn, mọi lựa chọn hợp lệ. Lưu ý $T$ có thể tới $2 \cdot 10^6 \cdot 10^9 = 2 \cdot 10^{15}$ nên mọi tổng đều phải là long long.
Cách 1Vét cạn O(n³)
Thử mọi đoạn $[l, r]$, mỗi đoạn dùng thêm một vòng lặp tính lại tổng và giá trị nhỏ nhất, rồi kiểm tra 2 lựa chọn ở trên.
Kết quả chạy thật: đúng 40/100 test: qua hết các test có $n \le 1000$ (test 1 – 40, chậm nhất khoảng 0,13 giây), từ $n = 10^4$ (test 41) trở đi quá thời gian.
Cách 2Bỏ vòng lặp thừa – O(n²)
Khi cố định $l$ và tăng dần $r$, đoạn $[l, r]$ chỉ là đoạn $[l, r - 1]$ thêm một cây $a_r$. Vậy tổng và min được cập nhật ngay: s += a[r]; mn = min(mn, a[r]);, không cần tính lại từ đầu. Thêm một mẹo nhỏ: khi số cây phải đốn ít nhất của đoạn (là len - 1) đã không nhỏ hơn đáp án hiện tại thì kéo dài thêm cũng vô ích, break luôn.
Kết quả chạy thật: bản C++ đúng 50/100 test: qua thêm 10 test $n = 10^4$ (chậm nhất khoảng 0,12 giây), nhưng từ $n = 10^5$ (test 51) thì $n^2 / 2$ đã là $5 \cdot 10^9$ phép tính – quá thời gian. Mẹo break không giúp được vì đáp án xấp xỉ $n/2$. Bản Python đúng 40/100 (chỉ tới $n = 1000$).
Ý tưởngTính đơn điệu và hai con trỏ
Để xuống được $O(n)$ hay $O(n \log n)$, ta cần một nhận xét then chốt:
Hệ quả: nếu đoạn $[l, r]$ đã đạt điều kiện thì mọi đoạn chứa nó cũng đạt. Khi $r$ tăng, vị trí $l$ xa nhất còn đạt điều kiện cũng chỉ tiến lên, không bao giờ lùi. Đó chính là kỹ thuật hai con trỏ (cửa sổ trượt):
- Lần lượt đẩy $r = 1, 2, \ldots, n$, thêm $a_r$ vào cửa sổ.
- Chừng nào cửa sổ $[l, r]$ còn đạt điều kiện: ghi nhận đáp án, rồi bỏ $a_l$ ra và tăng $l$ (thử đoạn ngắn hơn).
Mỗi phần tử vào cửa sổ 1 lần, ra 1 lần, nên chỉ có $O(n)$ bước. Ta chạy 2 lượt: lượt 1 cho lựa chọn "đốn hết" (điều kiện $2S \ge T$, ghi nhận $r - l + 1$), lượt 2 cho lựa chọn "bỏ qua 1 cây" (điều kiện $2(S - \min) \ge T$, ghi nhận $r - l$). Khó khăn duy nhất: lượt 2 phải biết min của cửa sổ ngay lập tức, trong khi cửa sổ vừa thêm bên phải vừa bớt bên trái.
Em nhập dãy rồi bấm Tiếp để xem hai con trỏ chạy qua cả 2 lượt (ô gạch ngang là cây nhỏ nhất được bỏ qua):
Cách 3Hai con trỏ + multiset – O(n log n)
Đúng tinh thần chương Map/Set: cho mọi cây trong cửa sổ vào một multiset. Multiset luôn tự sắp xếp tăng dần và cho phép trùng giá trị, nên *ms.begin() chính là cây nhỏ nhất. Thêm cây: ms.insert(a[r]); bớt cây: ms.erase(ms.find(a[l])).
- Phải viết
ms.erase(ms.find(a[l]))chứ không được viếtms.erase(a[l]): cách sau xoá tất cả các phần tử có giá trị bằnga[l], sai ngay khi có 2 cây cùng số bó. - Điều kiện
ms.size() >= 2: đoạn chỉ có 1 cây thì bỏ qua nó là chẳng đốn gì cả. - Lượt 1 không cần multiset vì không quan tâm min.
Kết quả chạy thật: đúng 85/100 test: các test $n = 10^5$ chỉ mất khoảng 0,09 giây, nhưng với $n = 10^6$ và $2 \cdot 10^6$ (test 86 – 100) thì mất khoảng 1,7 – 2 giây – quá giới hạn 1 giây. Multiset là cây nhị phân cân bằng, mỗi thao tác $O(\log n)$ kèm cấp phát bộ nhớ cho từng nút, nên với hàng triệu thao tác thì không kịp.
Cách 4Hàng đợi đơn điệu – O(n)
Ta không cần cả một cây nhị phân như multiset, chỉ cần min của một cửa sổ trượt. Công cụ chuẩn cho việc này là hàng đợi đơn điệu (monotonic deque): lưu các chỉ số sao cho giá trị $a$ tương ứng tăng dần từ đầu tới cuối hàng đợi.
- Thêm cây $r$: chừng nào cây ở cuối hàng đợi có $a \ge a_r$ thì bỏ nó đi – nó vào trước, ra trước $r$ mà lại không nhỏ hơn $a_r$, nên sẽ không bao giờ là min nữa. Rồi đẩy $r$ vào cuối.
- Lấy min: chính là cây ở đầu hàng đợi.
- Bỏ cây $l$ ra khỏi cửa sổ: nếu đầu hàng đợi đúng là $l$ thì bỏ nó đi.
Mỗi chỉ số vào và ra hàng đợi tối đa 1 lần nên tổng cộng $O(n)$. Mình cài hàng đợi bằng mảng dq với 2 biến h (đầu), t (cuối) cho nhanh. Em bấm Tiếp để xem hàng đợi thay đổi thế nào ở lượt 2:
Kết quả chạy thật: bản C++ đúng 100/100 test, test chậm nhất ($n = 2 \cdot 10^6$) chạy khoảng 0,21 giây, phần lớn là thời gian đọc dữ liệu. Bản Python cùng thuật toán đúng 89/100: các test $n = 10^6$ mất khoảng 1 giây (4/10 test lọt), 5 test $n = 2 \cdot 10^6$ mất khoảng 1,9 giây – Python không kịp đọc và xử lý 2 triệu số trong 1 giây.
Nhận xét
Đăng nhận xét