Hướng dẫn giải của Câu 3 (Tuyển sinh chuyên Tin Bình Dương 2022-2023)
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 thời điểm ~i~ được chọn để bán khi giá tại ~i~ không nhỏ hơn giá của hai thời điểm lân cận ~i-1~ và ~i+1~. Ví dụ: dãy ~1, 2, 5, 4, 3, 3, 6, 6, 2~ có ba thời điểm thỏa mãn là giá 5, 6, 6. Lưu ý giá 6 thứ nhất được chọn dù bằng giá láng giềng bên phải, nên điều kiện là "không nhỏ hơn", không phải "lớn hơn hẳn".
Sub 1: Vét cạn — ~O(N^2)~, dùng khi ~N \le 5000~
Với mỗi thời điểm ~i~, duyệt cả dãy để tìm hai lân cận ~i-1~ và ~i+1~ rồi so sánh giá. Chỉ xét ~i~ có đủ hai lân cận. Nếu chỉ nộp sub này: đúng 49/50 test (1 test lớn bị quá giờ).
Sub 2: Kiểm tra trực tiếp — ~O(N)~
Duyệt ~i = 2, \ldots, N-1~, nếu ~a_i \ge a_{i-1}~ và ~a_i \ge a_{i+1}~ thì tăng bộ đếm. Thời điểm đầu và cuối không có đủ hai lân cận nên không được tính. Nếu chỉ nộp sub này: đúng 50/50 test.
Chương trình hoàn chỉnh
main đọc ~N~ và dãy giá. Nếu ~N \le 5000~ gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
int a[50005]; // gia hoa tai moi thoi diem
// Sub 1: vet can O(n^2) - voi moi thoi diem i, duyet ca day de tim hai lan can i-1 va i+1
void sub1() {
int cnt = 0;
for (int i = 1; i <= n; i++) {
bool ok = true;
bool hasLeft = false, hasRight = false;
for (int j = 1; j <= n; j++) {
if (j == i - 1) { hasLeft = true; if (a[i] < a[j]) ok = false; }
if (j == i + 1) { hasRight = true; if (a[i] < a[j]) ok = false; }
}
if (hasLeft && hasRight && ok) cnt++; // chi xet thoi diem co du hai lan can
}
cout << cnt << "\n";
}
// Sub 2: kiem tra truc tiep voi hai lan can - O(n)
void sub2() {
int cnt = 0;
for (int i = 2; i <= n - 1; i++)
if (a[i] >= a[i - 1] && a[i] >= a[i + 1]) cnt++;
cout << cnt << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 5000) sub1(); // du lieu nho
else sub2(); // du lieu lon
return 0;
}
Bình luận