Hướng dẫn giải của [VTT Q4 Contest 04] Bài 4: Xây dựng trạm phát sóng [STATION]
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cần chọn ít trạm nhất sao cho mọi tọa độ nguyên từ 0 đến ~n-1~ nằm trong đoạn ~[x - R, x + R]~ của ít nhất một trạm. Đây là bài phủ đoạn thẳng, giải bằng tham lam trái sang phải. In các chỉ số theo thứ tự tăng của tọa độ để khớp đáp án mẫu (máy chấm thật có checker nhận nhiều đáp án).
Sub 1: Tham lam quét toàn bộ — ~O(m \cdot k)~, dùng khi ~n, m \le 10^3~
Gọi ~cur~ là khu dân cư nhỏ nhất chưa có sóng (ban đầu 0). Mỗi bước quét cả ~m~ vị trí, trong các trạm phủ được ~cur~ (tức ~x - R \le cur \le x + R~) chọn trạm có ~x~ lớn nhất, rồi đặt ~cur = x + R + 1~, lặp đến khi ~cur \ge n~. Nếu chỉ nộp sub này: đúng 11/20 test.
Sub 2: Sắp xếp rồi tham lam một chiều — ~O(m \log m)~
Sắp xếp các vị trí theo tọa độ. Dùng một con trỏ chạy một chiều: ở mỗi bước đẩy con trỏ qua mọi trạm có ~x - R \le cur~, trạm cuối cùng được đẩy qua là trạm xa nhất, chọn nó và cập nhật ~cur = x + R + 1~. Mỗi trạm chỉ bị duyệt một lần nên rất nhanh. Bẫy: dùng ~long long~ vì ~x + R~ có thể đến ~2 \cdot 10^9~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu; ~n, m \le 1000~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n, m;
long long R;
long long x[1000005];
int ord[1000005];
// Sub 1: mỗi bước quét toàn bộ m vị trí để chọn trạm tham lam — ~O(m * k)~
void sub1() {
vector<int> res;
long long cur = 0; // khu dân cư nhỏ nhất chưa có sóng
while (cur < n) {
int pick = -1;
for (int i = 1; i <= m; i++)
if (x[i] - R <= cur && x[i] + R >= cur) // trạm phủ được cur
if (pick == -1 || x[i] > x[pick]) pick = i; // chọn trạm vươn xa nhất về bên phải
if (pick == -1) break; // (đề đảm bảo không xảy ra)
res.push_back(pick);
cur = x[pick] + R + 1;
}
cout << res.size() << "\n";
for (int v : res) cout << v << " ";
cout << "\n";
}
// Sub 2: sắp xếp vị trí theo tọa độ, tham lam với một con trỏ chạy một chiều — ~O(m \log m)~
void sub2() {
for (int i = 1; i <= m; i++) ord[i] = i;
sort(ord + 1, ord + m + 1, [&](int p, int q) {
if (x[p] != x[q]) return x[p] < x[q];
return p < q;
});
vector<int> res;
long long cur = 0;
int j = 1, last = -1;
while (cur < n) {
// đưa con trỏ qua mọi trạm có x - R <= cur, nhớ trạm cuối (xa nhất)
while (j <= m && x[ord[j]] - R <= cur) { last = ord[j]; j++; }
if (last == -1 || x[last] + R < cur) break; // (đề đảm bảo không xảy ra)
res.push_back(last);
cur = x[last] + R + 1;
}
cout << res.size() << "\n";
for (int v : res) cout << v << " ";
cout << "\n";
}
int main() {
freopen("STATION.INP", "r", stdin);
freopen("STATION.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m >> R;
for (int i = 1; i <= m; i++) cin >> x[i];
if (n <= 1000 && m <= 1000) sub1();
else sub2();
}
Bình luận