Nhỏ hơn

Tác giả:

Dạng bài

Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy số nguyên dương gồm \(N\) phần tử \(a_1,a_2,...,a_N\). Với mỗi chỉ số \(1 \le i \le N\) đếm xem có bao nhiêu phần tử bé hơn \(a_i\).

Input

Dòng đầu tiên gồm số nguyên dương \(N\) \((2 \le N \le 10^5)\)
Dòng thứ hai gồm \(N\) số nguyên dương \(a_1,a_2,...,a_N\) \((a_i \le 10^9)\)

Output

In ra \(N\) số nguyên, số thứ \(i\) cho biết số phần tử nhỏ hơn \(a_i\).

Scoring

Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^3\)
Subtask \(2\) (\(50\%\) số điểm): không ràng buộc gì thêm.

Example

Test 1

Input

5
3 2 1 1 2

Output

4 2 0 0 2

Bình luận

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

7

Small 11:32 a.m. 10 Tháng 6, 2020

Mục đích của bài này là dành cho HS THCS luyện về sắp xếp thôi. Nhiều em chưa học CTDL \(map\).

3

SPyofgame 1:43 p.m. 10 Tháng 6, 2020

Vâng thầy, giờ em viết luôn thầy

7

Small 2:35 p.m. 10 Tháng 6, 2020 ← đã chỉnh sửa →

Thầy cần liên lạc riêng với em:
Em có thể nhắn tin qua FB của thầy: https://www.facebook.com/dovannho

4

SPyofgame 4:22 p.m. 10 Tháng 6, 2020 ← đã chỉnh sửa →

Vâng thầy. Em đã biết thầy thông qua bạn Hiếu ạ UwU

5 bình luận nữa