Hướng dẫn giải của [200 đề thầy Đức] Bài 26: Tưới vườn
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Sau t giây, vòi tại luống x tưới các luống trong đoạn [x - (t-1), x + (t-1)]. Cần tìm t nhỏ nhất để mọi luống đều được tưới.
Sub 1: Thử từng giây và đánh dấu — ~O(T \cdot n \cdot k)~
Với t = 1, 2, ..., đánh dấu các luống được tưới rồi kiểm tra đủ n luống chưa. Đạt 29/29 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
vector<int> x(k);
for (auto &v : x) cin >> v;
// Vét cạn: thử t = 1, 2, ... ; sau t giây vòi tại x tưới các luống trong [x - (t-1), x + (t-1)]
for (int t = 1;; t++) {
vector<bool> wet(n + 1, false);
for (int xi : x)
for (int j = 1; j <= n; j++)
if (abs(j - xi) <= t - 1) wet[j] = true;
bool all = true;
for (int j = 1; j <= n; j++)
if (!wet[j]) all = false;
if (all) {
cout << t << "\n";
break;
}
}
}
return 0;
}
Sub 2: Công thức khoảng cách — ~O(n)~
Gọi r = t - 1 là bán kính tưới. Cần r \ge x1 - 1 (đầu dãy), r \ge n - xk (cuối dãy), và với hai vòi liên tiếp có g luống trống giữa chúng thì 2r \ge g, tức r \ge ~\lceil g/2 \rceil~. Đáp án là r lớn nhất trong các giá trị đó cộng 1. Đạt 29/29 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
vector<int> x(k);
for (auto &v : x) cin >> v;
// Sau t giây, mỗi vòi tưới bán kính r = t - 1 về hai phía.
// Cần r đủ lớn để phủ: đầu dãy (x1 - 1 luống), cuối dãy (n - xk luống),
// và khoảng trống giữa hai vòi liên tiếp có g luống, cần 2r >= g.
int r = max(x[0] - 1, n - x[k - 1]);
for (int i = 0; i + 1 < k; i++) {
int g = x[i + 1] - x[i] - 1;
r = max(r, (g + 1) / 2); // r >= ceil(g / 2)
}
cout << r + 1 << "\n";
}
return 0;
}
Bình luận