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.

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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.