Hướng dẫn giải của Mảng_HN


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.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, 111_LeQuangTam, OyamaGust, chaos

Hiểu bài toán

Bài toán yêu cầu tìm giá trị trung gian Y tối ưu để điều chỉnh hai mảng A và B. Cụ thể, ta cần chuyển đổi các phần tử trong mảng A sao cho chúng không vượt quá Y (nếu phần tử A[i] < Y thì tăng lên Y) và các phần tử trong mảng B sao cho chúng không nhỏ hơn Y (nếu B[j] > Y thì giảm xuống Y). Mục tiêu là tìm giá trị Y使得 tổng chi phí điều chỉnh là nhỏ nhất. Chi phí định nghĩa là tổng khoảng cách giữa các giá trị ban đầu và giá trị Y (tức là tổng lượng thay đổi).

Các cách tiếp cận

Cách Tối ưu hóa Tuyến tính (Tìm kiếm giá trị tối ưu)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<ll> A, B;
int n, m;

ll cost(ll T) {
    ll res = 0;
    for (ll x : A) if (x < T) res += (T - x);
    for (ll y : B) if (y > T) res += (y - T);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("MANG.INP", "r", stdin);
    freopen("MANG.OUT", "w", stdout);

    cin >> n >> m;
    A.resize(n);
    B.resize(m);

    for (int i = 0; i < n; i++) cin >> A[i];
    for (int j = 0; j < m; j++) cin >> B[j];

    ll low = *min_element(A.begin(), A.end());
    ll high = *max_element(B.begin(), B.end());

    if (low >= high) {
        cout << 0;
        return 0;
    }

    // Ternary search (Tìm kiếm 1/3)
    while (high - low > 2) {
        ll mid1 = low + (high - low) / 3;
        ll mid2 = high - (high - low) / 3;
        if (cost(mid1) < cost(mid2))
            high = mid2;
        else
            low = mid1;
    }

    ll ans = 1e18;
    for (ll i = low; i <= high; i++) {
        ans = min(ans, cost(i));
    }
    cout << ans;
    return 0;
}
  • Time Complexity: O((n+m) log V) (với V là khoảng giá trị tìm kiếm)
  • Space Complexity: O(n+m)

Hàm chi phí cost(T) có dạng hình chữ U (unimodal). Khi T tăng, chi phí cho mảng A tăng (vì phải tăng các phần tử lên T), còn chi phí cho mảng B giảm (vì giảm các phần tử xuống T). Do đó, hàm này có cực tiểu. Ta có thể sử dụng thuật toán Ternary Search (tìm kiếm 1/3) để tìm giá trị T tối ưu trong khoảng [min(A), max(B)]. Sau khi tìm được khoảng chứa giá trị tối ưu, ta duyệt qua các giá trị còn lại để tìm chính xác đáp án.

Cách Tối ưu hóa Đơn giản (Duyệt qua Candidate)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("mang.inp", "r", stdin);
    freopen("mang.out", "w", stdout);

    int n, m;
    cin >> n >> m;

    vector<long long> A(n), B(m);
    for (auto &x : A) cin >> x;
    for (auto &x : B) cin >> x;

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    vector<long long> prefA(n + 1), prefB(m + 1);
    for (int i = 1; i <= n; i++) prefA[i] = prefA[i - 1] + A[i - 1];
    for (int i = 1; i <= m; i++) prefB[i] = prefB[i - 1] + B[i - 1];

    vector<long long> candidates;
    for (auto x : A) candidates.push_back(x);
    for (auto x : B) candidates.push_back(x);
    sort(candidates.begin(), candidates.end());
    candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());

    long long ans = LLONG_MAX;

    for (long long Y : candidates) {
        // Tính chi phí nhanh bằng mảng tiền tố
        long long posA = lower_bound(A.begin(), A.end(), Y) - A.begin();
        long long cntA = n - posA; 
        long long sumA = prefA[n] - prefA[posA];
        long long costA = cntA * Y - sumA;

        long long posB = lower_bound(B.begin(), B.end(), Y) - B.begin();
        long long cntB = posB;
        long long sumB = prefB[posB];
        long long costB = sumB - cntB * Y;

        if (costA + costB < ans) ans = costA + costB;
    }
    cout << ans;
    return 0;
}
  • Time Complexity: O((n+m) log (n+m))
  • Space Complexity: O(n+m)

Giả thuyết là giá trị Y tối ưu luôn nằm trong tập hợp các giá trị xuất hiện trong mảng A hoặc mảng B. Ta tạo một danh sách 'candidates' chứa tất cả các giá trị duy nhất từ A và B. Sau đó, ta sắp xếp A và B, xây dựng mảng tiền tố (prefix sums) để tính chi phí cho mỗi giá trị Y candidate trong thời gian O(log n). Với mỗi Y, chi phí cho A là tổng (Y - A[i]) với A[i] < Y, và chi phí cho B là tổng (B[j] - Y) với B[j] > Y.

Cách Tham lam (Tìm điểm cân bằng)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen("MANG.INP", "r", stdin);
    freopen("MANG.OUT", "w", stdout);

    int n, m;
    cin >> n >> m;
    vector<ll> a(n), b(m);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    // Hai con trỏ
    int i = 0;          // Duyệt mảng a (các phần tử nhỏ cần tăng lên)
    int j = m - 1;      // Duyệt mảng b (các phần tử lớn cần giảm xuống)

    ll ans = 0;
    // Logic: Cân bằng lượng tăng và giảm
    // Nếu a[i] < b[j], ta có thể chọn một giá trị Y nằm giữa chúng.
    // Tuy nhiên, bài toán yêu cầu Y phải chung cho tất cả.
    // Phân tích thêm: Hàm chi phí là lồi (convex). 
    // Ta có thể dùng Binary Search hoặc Ternary Search như Approach 1.
    // Code dưới đây là một biến thể của việc tìm Y tối ưu bằng cách duyệt.

    // Tuy nhiên, một cách tiếp cận khác (không thấy trong code mẫu nhưng hợp lý) là:
    // Suy nghĩ lại: Nếu chỉ cần tối thiểu hóa tổng số bước,
    // ta cần tìm Y sao cho số lượng phần tử A[i] < Y và B[j] > Y được cân bằng về mặt chi phí.
    // Thực tế, Y tối ưu nằm giữa max(A) và min(B) nếu chúng giao nhau.
    // Nếu không giao nhau, Y nằm ở điểm giữa.

    // Code minh họa cho Approach 1 (Ternary Search) là chuẩn nhất.
    // Dưới đây là code minh họa cho việc dùng Lower Bound để tìm điểm chuyển dịch của chi phí.

    // Giả định: Y tối ưu nằm trong [min(A), max(B)]
    ll lo = *min_element(a.begin(), a.end());
    ll hi = *max_element(b.begin(), b.end());

    // Nếu tất cả A đều >= B, chi phí là 0
    if (lo >= hi) {
        cout << 0 << endl;
        return 0;
    }

    // Binary Search cho điểm giao của hàm chi phí
    // Hoặc đơn giản là tìm Y sao cho tổng A[i] < Y gần bằng tổng B[j] > Y
    // Code này thực chất là tìm Y sao cho 'lợi nhuận' cân bằng.

    // Tuy nhiên, do hàm chi phí là lồi, Ternary Search là cách dễ nhất để hiện thực.
    // Dưới đây là code sử dụng Binary Search trên Gradient (Đạo hàm).
    // Chi phí tăng thêm khi Y tăng từ T lên T+1 là: 
    //  (số phần tử A[i] <= T) - (số phần tử B[j] > T)
    // Ta cần tìm điểm mà giá trị này gần 0 nhất.

    while (lo < hi) {
        ll mid = lo + (hi - lo) / 2;
        // Đếm số lượng A[i] <= mid
        ll countA = upper_bound(a.begin(), a.end(), mid) - a.begin();
        // Đếm số lượng B[j] > mid
        ll countB = b.end() - upper_bound(b.begin(), b.end(), mid);

        if (countA > countB) {
            // Có quá nhiều A cần tăng, chi phí tăng thêm khi Y tăng là dương (cần giảm Y)
            hi = mid;
        } else {
            // Có quá nhiều B cần giảm, chi phí tăng thêm khi Y tăng là âm (cần tăng Y)
            lo = mid + 1;
        }
    }

    // Tính chi phí tại lo
    ll cost = 0;
    for (ll x : a) if (x < lo) cost += (lo - x);
    for (ll x : b) if (x > lo) cost += (x - lo);
    cout << cost << endl;
    return 0;
}
  • Time Complexity: O((n+m) log (n+m))
  • Space Complexity: O(n+m)

Hàm chi phí có tính chất đơn điệu (monotonic gradient) hoặc lồi. Khi Y tăng từ rất nhỏ lên rất lớn, chi phí tăng của A (số phần tử cần tăng) tăng dần, còn chi phí giảm của B (số phần tử cần giảm) giảm dần. Ta có thể dùng Binary Search để tìm điểm mà sự thay đổi chi phí chuyển từ âm sang dương (điểm cực tiểu). Cụ thể, ta tìm giá trị Y sao cho số lượng phần tử A cần tăng bằng số lượng phần tử B cần giảm. Nếu số lượng A cần tăng > B cần giảm, ta cần giảm Y để giảm chi phí A (vì A có nhiều phần tử nhỏ, chi phí tăng Y lớn). Ngược lại, ta tăng Y.

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O((n+m) log V) (với V là khoảng giá trị tìm kiếm) O(n+m) Tối ưu hóa Tuyến tính (Tìm kiếm giá trị tối ưu)
2 O((n+m) log (n+m)) O(n+m) Tối ưu hóa Đơn giản (Duyệt qua Candidate)
3 O((n+m) log (n+m)) O(n+m) Tham lam (Tìm điểm cân bằng)

Bài học kinh nghiệm

  • Hàm chi phí tổng quát là lồi (convex/unimodal). Điều này cho phép chúng ta áp dụng các thuật toán tìm kiếm tối ưu như Ternary Search hoặc Binary Search trên đạo hàm.
  • Giá trị Y tối ưu thường nằm trong khoảng [min(A), max(B)]. Nếu min(A) >= max(B), chi phí là 0.
  • Sử dụng mảng tiền tố (Prefix Sums) kết hợp với Suy giảm (Binary Search) giúp tính chi phí cho một giá trị Y cụ thể trong thời gian O(log n) thay vì O(n).

Lỗi thường gặp

  • Sử dụng kiểu dữ liệu int cho biến tổng chi phí hoặc các giá trị đầu vào lớn (nên dùng long long).
  • Xử lý sai trường hợp các mảng giao nhau hoặc không giao nhau (cần kiểm tra điều kiện biên trước).
  • Trong Binary Search/Ternary Search, người giải có thể bị kẹt trong vòng lặp vô hạn nếu không cập nhật khoảng tìm kiếm đúng cách (off-by-one errors).

Bình luận

Please read the guidelines before commenting.


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