Hướng dẫn giải của [200 đề thầy Đức] Bài 196: Ngày xấu
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
Ngày ~i~ là ngày xấu nếu có một ngày sau đó có giá thấp hơn ~a_i~. Đếm số ngày xấu của từng truy vấn.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Với mỗi ngày ~i~, quét các ngày sau; gặp ngày có giá nhỏ hơn ~a_i~ thì đếm và dừng. Nếu chỉ nộp sub này: đúng 11/21 test, các test lớn bị quá giờ.
Sub 2: Giá nhỏ nhất phía sau — ~O(n)~
Duyệt từ cuối về đầu, giữ giá nhỏ nhất của các ngày phía sau. Ngày ~i~ là ngày xấu khi giá nhỏ nhất đó nhỏ hơn ~a_i~. Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
main đọc ~q~ truy vấn. Với mỗi truy vấn, nếu ~n \le 1000~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[100005];
// Sub 1: vét cạn O(n^2). Ngày i xấu nếu có ngày j > i với giá a[j] < a[i].
void sub1() {
int cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
if (a[j] < a[i]) {
cnt++;
break;
}
printf("%d\n", cnt);
}
// Sub 2: O(n). Duyệt từ cuối về đầu, giữ giá nhỏ nhất của các ngày phía sau.
// Ngày i xấu khi giá nhỏ nhất phía sau nhỏ hơn a[i].
void sub2() {
int cnt = 0;
long long sufMin = LLONG_MAX;
for (int i = n; i >= 1; i--) {
if (sufMin < a[i]) cnt++;
sufMin = min(sufMin, a[i]);
}
printf("%d\n", cnt);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 1000) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
}
return 0;
}
Bình luận