Nhỏ hơn

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
admin
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

  • leminhduc • 9:50 p.m. 16 Tháng 11, 2024 •

    Bài này hay nhất là dùng lower_bound

    0
    Phản hồi
    • haichamchi2010 • 10:16 p.m. 4 Tháng 6, 2024 •

      This comment is hidden due to too much negative feedback. Click here to view it.

      -5
      Phản hồi
      • kimanhctt2 • 2:56 p.m. 7 Tháng 1, 2024 •

        hyt

        0
        Phản hồi
        • xthabao1 • 10:32 p.m. 10 Tháng 8, 2023 •

          test sai sai

          0
          Phản hồi
          • Dolaminro • 2:50 p.m. 4 Tháng 4, 2023 •

            bài này quy hoạch động ac nè

            0
            Phản hồi
            • mcsmuscle • 9:39 a.m. 2 Tháng 11, 2021 • ← đã chỉnh sửa

              ...

              0
              Phản hồi
              • SPyofgame • 10:49 p.m. 4 Tháng 6, 2020 • ← chỉnh sửa 12

                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] << ' ';
                20
                Phản hồi
                • Yucy • 8:41 p.m. 28 Tháng 4, 2020 •

                  Cho em hỏi hình như test 9 và 10 của bài này hình như a[i] có = 0 đúng không ạ? tại em code thôi đề là nguyên dương thì wa 2 test đó còn khi em code có thêm trường hợp ai = 0 thì ac :'(. Không biết có phải là do em code sai không nữa

                  6
                  Phản hồi