Hướng dẫn giải của [Beginner Free Contest 01] HEIGHT
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
Với mỗi học sinh ~i~ cần đếm số học sinh có chiều cao nhỏ hơn ~A_i~.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Với mỗi ~i~, duyệt toàn bộ ~j~ và đếm ~A_j < A_i~. Nếu chỉ nộp sub này: đúng 5/10 test.
Sub 2: Sắp xếp và tìm kiếm nhị phân — ~O(n \log n)~
Sắp xếp bản sao của dãy, số học sinh thấp hơn ~A_i~ chính là vị trí đầu tiên có giá trị ~A_i~ (dùng ~lower_bound~). Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
~main~ đọc dãy, nếu ~N \le 1000~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long A[100005]; // A[1..n]
// Sub 1: vet can O(n^2) (n <= 1000): voi moi i, dem j co A[j] < A[i]
void sub1() {
for (int i = 1; i <= n; i++) {
int cnt = 0;
for (int j = 1; j <= n; j++)
if (A[j] < A[i]) cnt++;
cout << cnt << (i == n ? '\n' : ' ');
}
}
// Sub 2: O(n log n): sap xep ban sao, lower_bound cho biet co bao nhieu phan tu nho hon A[i]
void sub2() {
vector<long long> s(A + 1, A + n + 1);
sort(s.begin(), s.end());
for (int i = 1; i <= n; i++) {
int cnt = lower_bound(s.begin(), s.end(), A[i]) - s.begin();
cout << cnt << (i == n ? '\n' : ' ');
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> A[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận