Hướng dẫn giải của KS Câu 3: Nén mảng
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
Cần đổi dãy ~A~ thành dãy ~B~ sao cho: mọi ~B_i \in [1, n]~; nếu ~A_i \le A_j~ thì ~B_i \le B_j~; và các ~B_i~ nhỏ nhất có thể. Cách làm tự nhiên là đánh thứ hạng dày đặc: ~B_i~ bằng số giá trị khác nhau nhỏ hơn hoặc bằng ~A_i~. Cách này cho giá trị nhỏ nhất và luôn nằm trong ~[1, n]~; các phần tử bằng nhau nhận cùng một ~B~.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 5000~
Trước hết đánh dấu mỗi giá trị chỉ được tính một lần (ở lần xuất hiện đầu tiên). Với mỗi ~i~, duyệt cả dãy đếm các giá trị đã đánh dấu và nhỏ hơn ~A_i~, rồi cộng 1. Nếu chỉ nộp sub này: đúng 8/8 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, bỏ các phần tử trùng (unique). Với mỗi ~A_i~, dùng lower_bound để tìm vị trí của nó trong dãy đã bỏ trùng; ~B_i~ bằng vị trí đó cộng 1.
Bẫy cần chú ý: các giá trị có thể âm, không được giả định ~A_i \ge 1~; phải bỏ trùng trước khi tìm vị trí, nếu không thứ hạng sẽ sai.
Nếu chỉ nộp sub này: đúng 8/8 test.
Chương trình hoàn chỉnh
main đọc ~n~ và dãy ~A~. Nếu ~n \le 5000~ thì gọi sub1, còn lại gọi sub2. Sau đó in dãy ~B~.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[100005]; // day A dau vao
long long b[100005]; // day B sau khi nen
// Sub 1: vet can O(n^2) - B_i = 1 + so gia tri khac nhau nho hon A_i.
// Danh dau moi gia tri chi dem mot lan (lan xuat hien dau tien).
void sub1() {
vector<bool> first(n + 1, false);
for (int j = 1; j <= n; j++) {
first[j] = true;
for (int k = 1; k < j; k++)
if (a[k] == a[j]) { first[j] = false; break; }
}
for (int i = 1; i <= n; i++) {
long long cnt = 1;
for (int j = 1; j <= n; j++)
if (first[j] && a[j] < a[i]) cnt++;
b[i] = cnt;
}
}
// Sub 2: sap xep, bo trung, roi tim vi tri cua moi A_i bang lower_bound - O(n log n)
void sub2() {
vector<long long> v(a + 1, a + n + 1);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 1; i <= n; i++)
b[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
// Mang nho (n <= 5000): sub1; mang lon: sub2
if (n <= 5000) sub1();
else sub2();
for (int i = 1; i <= n; i++)
cout << b[i] << (i < n ? " " : "\n");
return 0;
}
Bình luận