Hướng dẫn giải của [200 đề thầy Đức] Bài 154: Những ngôi nhà có ánh nắng
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
Mặt trời chiếu từ bên trái. Ngôi nhà thứ ~j~ nhận nắng khi không có ngôi nhà nào bên trái nó cao hơn nó. Cần đếm số ngôi nhà nhận nắng.
Sub 1: Vét cạn kiểm tra mọi ngôi nhà bên trái — ~O(N^2)~
Với mỗi ngôi nhà ~j~, duyệt tất cả ngôi nhà ~i < j~ xem có ngôi nhà nào cao hơn không. Nếu không có thì ngôi nhà đó nhận nắng. Đạt 17/21 test, 4 test lớn quá giờ vì N lên tới 10^5.
#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;
cin >> n;
vector<int> h(n);
for (int &x : h) cin >> x;
// Vét cạn O(N^2): với mỗi ngôi nhà j, kiểm tra mọi ngôi nhà bên trái có cao hơn không
int ans = 0;
for (int j = 0; j < n; j++) {
bool shaded = false;
for (int i = 0; i < j && !shaded; i++) {
if (h[i] > h[j]) shaded = true;
}
if (!shaded) ans++;
}
cout << ans << "\n";
}
return 0;
}
Sub 2: Theo dõi chiều cao lớn nhất bên trái — ~O(N)~
Nhận xét: ngôi nhà ~j~ nhận nắng khi chiều cao của nó không nhỏ hơn chiều cao lớn nhất của các ngôi nhà đứng trước. Chỉ cần giữ một biến ~maxSoFar~ và cập nhật khi gặp ngôi nhà cao hơn hoặc bằng. Đạt 21/21 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;
cin >> n;
// Ngôi nhà j nhận nắng khi chiều cao không nhỏ hơn mọi ngôi nhà bên trái,
// tức là không nhỏ hơn chiều cao lớn nhất của các ngôi nhà trước nó.
int maxSoFar = 0;
int ans = 0;
for (int j = 0; j < n; j++) {
int h;
cin >> h;
if (h >= maxSoFar) {
ans++;
maxSoFar = h;
}
}
cout << ans << "\n";
}
return 0;
}
Bình luận