Editorial for Nhỏ hơn

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

`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] << ' ';

Comments

There are no comments at the moment.