Xây dựng trạm phát sóng
Đề bài
Xây dựng trạm phát sóng (Đề tuyển sinh lớp 10 trường Phổ thông Năng khiếu năm 2017 – 2018)
Wonder Land là một thành phố thông minh với nền tảng là các thiết bị công nghệ cao cùng với hệ thống phần mềm ứng dụng luôn kết nối internet cung cấp dịch vụ tiện ích cho mọi cư dân. Wonder Land có $n$ khu dân cư được quy hoạch cách đều nhau một đơn vị độ dài dọc theo một con đường thẳng tắp. Như vậy Wonder Land được biểu diễn bởi trục số và vị trí $n$ khu dân cư là các điểm có tọa độ nguyên liên tiếp từ $0$ đến $n - 1$.
Nhằm nâng cao tốc độ kết nối các dịch vụ, chính quyền lên kế hoạch xây dựng mới các trạm phát sóng di động thế hệ đột phá (Innovation Generation) sao cho mọi khu dân cư đều nhận được sóng. Mỗi trạm phát sóng phủ một vùng bán kính $R$ với tâm là trạm phát sóng và mọi khu dân cư có khoảng cách đến trạm phát sóng không lớn hơn $R$ đều nhận được sóng từ trạm đó. Sau một thời gian khảo sát, chính quyền có được danh sách $m$ vị trí trên trục đường có thể xây dựng trạm, vị trí thứ $i$ có tọa độ $x_i$. Nhà quản lý muốn chọn ra một số vị trí lắp đặt sao cho số trạm cần phải xây dựng là ít nhất và mọi khu dân cư đều nhận được sóng của ít nhất một trạm.
Chẳng hạn $n = 12$, có thể xây dựng trạm tại 8 vị trí với tọa độ là $3, 1, 0, 5, 9, 6, 10, 11$ với bán kính phát sóng $R = 2$ ta chỉ cần xây 3 trạm tại các tọa độ $1, 6, 11$, tương ứng tại các vị trí 2, 6 và 8 thì có thể phủ sóng cho tất cả khu dân cư.
Yêu cầu: Cho số khu dân cư $n$, dãy $m$ số nguyên $x_1, x_2, \ldots, x_m$ $(0 \le x_i \le n - 1;\ 1 \le m \le n)$ – tọa độ có thể xây dựng trạm phát sóng và số nguyên $R$ – bán kính phát sóng. Hãy tìm phương án chọn ra ít nhất các vị trí cần xây dựng trạm sao cho toàn bộ $n$ khu dân cư đều nhận sóng.
Dữ liệu: (tập tin STATION.INP)
- Dòng đầu ghi 3 số $n$, $m$ và $R$.
- Dòng thứ hai ghi $m$ số $x_1, x_2, \ldots, x_m$.
Kết quả: (tập tin STATION.OUT) ghi số $k$ – số trạm cần xây dựng.
Giới hạn: $1 \le n \le 10^6$. Subtask: 30% số test có $N \le 10^2$; 30% số test có $N \le 10^3$; 40% số test còn lại không có điều kiện gì thêm.
Giới hạn thời gian: 1 giây, bộ nhớ: 256 MB.
12 8 2
3 1 0 5 9 6 10 113- Kết quả chỉ cần xuất ra 1 số nguyên duy nhất là số trạm ít nhất cần xây dựng; nếu không thể phủ sóng hết toàn bộ thì xuất ra 0. Không cần xuất dòng thứ 2 (danh sách vị trí) như đề gốc – ví dụ mẫu chỉ cần in số 3.
- Dữ liệu đọc/ghi bằng file
STATION.INP/STATION.OUTgiống y như đề. Code của mình dùngif (fopen("STATION.INP", "r")) {...}nên có file thì dùng file, không có thì đọc bàn phím.
Lời mở đầu
Mỗi trạm ở tọa độ $x$ phủ một đoạn $[x - R,\ x + R]$ trên trục số. Bài toán trở thành: chọn ít đoạn nhất để phủ kín đoạn $[0, n - 1]$ – một bài phủ đoạn kinh điển giải bằng tham lam. Mình sẽ trình bày cách tham lam "ngây thơ" (mỗi bước duyệt lại cả danh sách trạm), rồi tối ưu bằng sắp xếp + con trỏ chạy một chiều.
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:
| Test | n | m | R | Đáp án | Số test in 0 |
|---|---|---|---|---|---|
| 1–10 | 3 … 10 | 3 … 10 | 0 … 8 | 0 … 9 | 1 |
| 11–30 | 32 … 100 | 27 … 98 | 0 … 5 | 10 … 34 | 0 |
| 31–60 | 218 … 976 | 188 … 732 | 1 … 20 | 22 … 122 | 0 |
| 61–80 | 2.617 … 32.149 | 587 … 21.052 | 2 … 225 | 49 … 617 | 0 |
| 81–90 | 101.892 … 130.327 | 2.041 … 22.670 | 18.959 … 120.110 | 0 … 1 | 2 |
| 91–99 | 1.000.000 | 5.646 … 29.381 | 970.747 … 996.402 | 1 | 0 |
| 100 | 1.000.000 | 1.000.000 | 0 | 1.000.000 | 0 |
- Subtask trong đề khớp với bộ test: test 1–30 có $n \le 100$, test 31–60 có $n \le 1000$, test 61–100 lớn hơn.
- Có 3 test in 0 (test 3, 81, 82): không có cách nào phủ hết, ví dụ $R = 0$ mà không phải khu nào cũng có trạm, hoặc có một khoảng trống quá dài.
- Test 81–99 có $R$ rất lớn (gần bằng $n$) nhưng các tọa độ trạm chỉ nằm trong khoảng $0 \ldots 32\,767$ – thường chỉ cần 1 trạm.
- Test 100 là test "nặng" nhất: $n = m = 10^6$, $R = 0$, mọi khu đều có trạm – đáp án là $10^6$ trạm.
- Trong bộ test các tọa độ $x_i$ đôi một khác nhau, nhưng thứ tự lộn xộn (chưa sắp xếp).
Kết quả chạy thật theo subtask (giới hạn 1 giây):
| Subtask | Đề ghi | Test | Cách 1 C++ | Cách 1 Python | Cách 2 C++ | Cách 2 Python |
|---|---|---|---|---|---|---|
| 1 (30%) | $N \le 10^2$ | 1–30 | 30/30 | 30/30 | 30/30 | 30/30 |
| 2 (30%) | $N \le 10^3$ | 31–60 | 30/30 | 30/30 | 30/30 | 30/30 |
| 3 (40%) | không giới hạn thêm ($N \le 10^6$) | 61–100 | 39/40 | 38/40 | 40/40 | 39/40 |
Ý tưởngTham lam: lo cho khu đầu tiên chưa có sóng
Xét từ trái sang phải. Gọi $p$ là khu dân cư đầu tiên chưa có sóng (lúc đầu $p = 0$). Chắc chắn phải có một trạm phủ được $p$, tức là trạm $x$ thoả $x - R \le p \le x + R$. Trong các trạm như vậy, nên chọn trạm nào?
Vì sao đúng? Giả sử phương án tối ưu dùng trạm $y$ để phủ $p$. Thay $y$ bằng trạm tham lam $x \ge y$: đoạn $[x - R, x + R]$ vẫn chứa $p$ và kéo xa hơn về bên phải, còn các khu bên trái $p$ đã có sóng sẵn – nên phương án mới vẫn phủ hết và không tốn thêm trạm. Lặp lại lập luận cho từng bước.
Em nhập dữ liệu rồi bấm Tiếp để xem từng bước chọn trạm (ô xanh là khu đã có sóng, ô vàng là khu $p$ đang cần sóng, 📡 là các vị trí có thể đặt trạm):
Cách 1Tham lam, mỗi bước duyệt cả m trạm – $O(k \cdot m)$
Cài đặt thẳng ý tưởng: mỗi lần cần phủ khu $p$, duyệt hết $m$ trạm để tìm trạm phủ được $p$ có tọa độ lớn nhất.
- Điều kiện
x[i] - R <= p && p <= x[i] + Rnghĩa là trạm $i$ phủ được khu $p$. best == -1sau vòng duyệt nghĩa là không có trạm nào phủ được $p$ → in 0 và kết thúc luôn.- Mỗi trạm được chọn phủ tới $best + R$, nên khu tiếp theo cần lo là $best + R + 1$.
Với $k$ là số trạm được chọn, mỗi bước tốn $O(m)$. Hầu hết các test có $k$ nhỏ (vài chục, vài trăm) nên rất nhanh; nhưng test 100 có $k = m = 10^6$ → $10^{12}$ phép tính!
Kết quả chạy thật: Bản C++ đúng 99/100 test, quá thời gian ở test 100; test đúng chạy lâu nhất 0.03s. Bản Python đúng 98/100 test, quá thời gian ở test 77, 100; test đúng chạy lâu nhất 0.38s. Cách 1 ăn trọn subtask 1, 2 và gần hết subtask 3.
Cách 2Sắp xếp + hai con trỏ – $O(m \log m)$
Sắp xếp các tọa độ tăng dần. Điều kiện "trạm phủ được $p$, lớn nhất" chính là: trạm cuối cùng có $x \le p + R$ (và phải có $x \ge p - R$). Khi $p$ tăng thì mốc $p + R$ cũng tăng, nên con trỏ $i$ trên mảng đã sắp xếp chỉ việc chạy tiếp về bên phải, không bao giờ quay lại – giống hệt một cửa sổ trượt.
- Vòng
while(i < m && x[i] <= p + R)đi qua mọi trạm có $x - R \le p$; trạm cuối cùng đi qua là trạm lớn nhất, lưu vàobest. - Các trạm bị con trỏ bỏ qua (nhỏ hơn
best) không bao giờ cần dùng lại: chúng phủ tới tối đa $best + R$, mà các khu đó đã có sóng. - Kiểm tra
best + R < p: trạm lớn nhất vẫn ở quá xa bên trái, không với tới $p$ → in 0. Nếubest == -1thì không có trạm nào mới trong khoảng này (trạm cũ đã dùng hoặc không có). - Tổng số lần
i++trong cả chương trình không quá $m$, nên phần tham lam chỉ $O(m)$; tốn nhất là bướcsort. (Vì $x_i < n \le 10^6$ nên cũng có thể đánh dấu bằng mảng thay cho sắp xếp để được $O(n)$.)
Kết quả chạy thật: Bản C++ đúng 100/100 test; test đúng chạy lâu nhất 0.11s. Bản Python đúng 99/100 test, quá thời gian ở test 100; test đúng chạy lâu nhất 0.05s.
Tổng kếtKết quả chạy thật trên bộ test
| Cách | Ngôn ngữ | Đúng | Lâu nhất | Ghi chú |
|---|---|---|---|---|
| 1. Tham lam, mỗi lần duyệt cả m trạm | C++ | 99/100 | > 1s | Quá thời gian test 100 |
| Python | 98/100 | > 1s | Quá thời gian test 77, 100 | |
| 2. Sắp xếp + hai con trỏ | C++ | 100/100 | 0.11s | Full điểm |
| Python | 99/100 | > 1s | Quá thời gian test 100 |
sys.stdin.buffer, nhưng với $10^6$ số thì riêng việc đọc + sắp xếp đã sát giới hạn.