Hướng dẫn giải của SETMAP06: Nén mả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
Nén mảng: ~B_i~ là thứ hạng của ~A_i~ trong dãy các giá trị khác nhau đã sắp xếp (từ 1). Đây là cách gán nhỏ nhất thỏa mãn điều kiện đề bài.
Sub 1: Vét cạn — ~O(n^2 \log n)~, dùng khi ~n \le 1000~
Với mỗi ~i~, quét cả dãy lấy các giá trị nhỏ hơn ~A_i~, loại trùng, rồi ~B_i~ = số giá trị đó + 1.
Nếu chỉ nộp sub này: đúng 6/10 test.
Sub 2: Nén tọa độ — ~O(n \log n)~
Sắp các giá trị khác nhau, sau đó tìm vị trí của ~A_i~ bằng tìm nhị phân (lower_bound) rồi cộng 1.
Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu rồi chọn sub theo kích thước: dữ liệu nhỏ gọi sub 1 (vét cạn), dữ liệu lớn gọi sub cuối. Khi đi thi, nên nộp đầy đủ như vậy: nếu sub sau sai hoặc chưa kịp làm thì vẫn ăn điểm các sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> A;
// Sub 1: vét cạn — B_i = 1 + số giá trị khác nhau nhỏ hơn A_i.
// Với mỗi i, quét cả dãy lấy các giá trị nhỏ hơn A_i, loại trùng rồi đếm. O(n^2 log n)
void sub1() {
for (int i = 0; i < n; i++) {
vector<long long> smaller;
for (int j = 0; j < n; j++)
if (A[j] < A[i]) smaller.push_back(A[j]);
sort(smaller.begin(), smaller.end());
smaller.erase(unique(smaller.begin(), smaller.end()), smaller.end());
cout << smaller.size() + 1 << (i == n - 1 ? "\n" : " ");
}
}
// Sub 2: nén tọa độ — sắp các giá trị khác nhau, B_i là vị trí (từ 1) của A_i trong dãy đó. O(n log n)
void sub2() {
vector<long long> v(A);
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for (int i = 0; i < n; i++) {
int pos = lower_bound(v.begin(), v.end(), A[i]) - v.begin();
cout << pos + 1 << (i == n - 1 ? "\n" : " ");
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
A.resize(n);
for (int i = 0; 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