Hướng dẫn cho Nhỏ hơn

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame

`Spoiler Alert`

Hint 1

Duyệt qua mảng đó, với mỗi phần tử ta đếm số lượng nhỏ hơn và xuất ra

Reference 90 score + TLE code | \(O(n ^ 2)\) time | \(O(n)\) query | \(O(1)\) auxiliary space | Brute-force

C++

/// Nhan mang
int n;
cin >> n;

int a[n + 1];
for (int i = 1; i <= n; ++i)
    cin >> a[i];

/// Xu li
for (int i = 1; i <= n; ++i)
{
    /// Voi moi phan tu, ta gan bien dem = 0
    int dem = 0;
    for (int j = 1; j <= n; ++j) /// Dem so luong aj < ai
        if (a[i] > a[j])
            dem++;

    /// Xuat ket qua
    cout << dem << ' ';
}
return 0;

Hint 2

Nhận thấy có tính chất bắc cầu a > b và b > c thì a > c

Ta vận dụng để tiếp cận bài toán theo hướng khác mà không phải tính lại các đoạn đằng trước

Hint 3

Tạo một mảng con B[] từ A[], gồm các phần tử đã được sắp xếp tăng dần

Gọi p là vị trí số lớn nhất trong B[i] bé hơn A[i]

Ta có số phần tử bé hơn A[i] là khoảng cách từ vị trí đầu của B[] tới p

Hint 4

Dùng chặt nhị phân, ta có thể tìm p nhanh hơn

Reference AC code | \(O(n\) \(log_2 n)\) time | \(O(log_2 n)\) query | \(O(n)\) auxiliary space | Sorting, Binary_search

C++

/// Nhan so phan tu
int n;
cin >> n;

/// Nhan mang
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i)
{
    cin >> a[i];
    b[i] = a[i];
}   
sort(b.begin(), b.end());

for (int i = 0; i < n; ++i)
{
    /// Xu li
    int p = -1;
    for (int l = -1, r = n - 1; l < r; )
    {
        int m = l + (r - l) / 2 + 1;
        if (a[i] > b[m])
            p = l = m;
        else
            r = m - 1;
    }

    /// Xuat ket qua
    cout << p + 1 << ' ';
}

Reference AC code | \(O(n\) \(log_2 n)\) time | \(O(1)\) query | \(O(n)\) auxiliary space | Sorting, Binary_search

C++

/// Nhan so phan tu
int n;
cin >> n;

/// Nhan mang
int a[n + 1], b[n + 1];
for (int i = 1; i <= n; ++i)
{
    cin >> a[i];
    b[i] = a[i];
}
sort(b + 1, b + n + 1);

/// Lay cac phan tu phan biet
int p = 1; /// so luong phan tu phan biet
for (int i = 2; i <= n; ++i)
    if (b[i] != b[i - 1]) /// khong lay cac phan tu trung nhau
        b[++p] = b[i];    /// them phan tu do vao mang

/// Xu li tinh toan: b[t[i]] = a[i]
int t[n + 1];
for (int i = 1; i <= n; ++i)
    t[i] = lower_bound(b + 1, b + p + 1, a[i]) - b;

/// Xu li tinh toan: c[t[i]] = number of element x less than or equal a[i] in array    
int c[p + 1];
for (int i = 0; i <= p; ++i) c[i] = 0;
for (int i = 1; i <= n; ++i) c[t[i]]++;
for (int i = 1; i <= p; ++i) c[i] += c[i - 1];

/// Xuat ket qua
for (int i = 1; i <= n; ++i)
    cout << c[t[i] - 1] << ' ';

Reference AC code | \(O(n\) \(log_2 n)\) time | \(O(1)\) query | \(O(n)\) auxiliary space | Sorting, Binary_search, STL

C++

/// n la so phan tu
int n;
cin >> n;

/// A[i] la phan tu thu (i) trong mang (a)
vector<int> a(n);
for (int &x : a) cin >> x;

/// M[x] la so phan tu bang (x) co trong mang (a)
map<int, int> M;
for (int x : a) M[x]++;

/// S[x] la so luong so be hon (x) trong mang (a)
unordered_map<int, int> S;
int cnt = 0;
for (pair<int, int> e : M)
{
    S[e.first] = cnt;
    cnt += e.second;
}

/// Xuat ket qua
for (int x : a) cout << S[x] << ' ';

Bình luận

Không có bình luận nào.