Editorial for spot: Cắm trại

Hiểu bài toán

Bài toán yêu cầu tìm một điểm tập trung (u, v)使得 tổng khoảng cách Manhattan (|xi - u| + |yi - v|) của N em bé đến điểm đó là nhỏ nhất. Với mỗi em bé tại (xi, yi), di chuyển theo 4 hướng (lên, xuống, trái, phải), chi phí di chuyển chính là khoảng cách Manhattan. Do đó, bài toán tách thành hai bài toán con độc lập tìm u tối ưu cho tọa độ x và v tối ưu cho tọa độ y để minimize tổng các giá trị absolutes.

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

Cách Median (Trung vị)

#include <bits/stdc++.h>
using namespace std;

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

    int N;
    cin >> N;
    vector<long long> X(N), Y(N);

    for (int i = 0; i < N; ++i)
        cin >> X[i] >> Y[i];

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());

    long long medianX = X[N / 2];
    long long medianY = Y[N / 2];

    long long res = 0;
    for (int i = 0; i < N; ++i)
        res += abs(X[i] - medianX) + abs(Y[i] - medianY);

    cout << res << "\n";
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Đây là cách tiếp cận trực quan và hiệu quả nhất. Tính chất then chốt là với một dãy số, trung vị (median) là giá trị minimize tổng khoảng cách absolutes (trục x và trục y làm việc độc lập). Ta chỉ cần sort hai mảng tọa độ x và y, lấy giá trị ở vị trí giữa (N/2). Nếu N chẵn, bất kỳ giá trị nào trong khoảng [x[N/2-1], x[N/2]] đều tối ưu, nhưng lấy giá trị tại chỉ số N/2 là đủ để tính tổng sai số tối thiểu. Độ phức tạp đến từ việc sort.

Cách Trung vị (Biến thể chỉ số 1-based)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5 + 5;
ll n, a[N], b[N], d = 0;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + 1 + n);
    ll u = a[(n + 1) / 2];
    ll v = b[(n + 1) / 2];
    for (int i = 1; i <= n; i++) d += abs(u - a[i]) + abs(v - b[i]);
    cout << d;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Cách giải này tương tự như cách trên, chỉ khác về cách xử lý chỉ số mảng (dùng 1-based thay vì 0-based). Công thức lấy trung vị là (n + 1) / 2. Logic toán học đằng sau hoàn toàn giống nhau: tìm giá trị trung gian để minimize tổng khoảng cách.

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

Bài học kinh nghiệm

• Bài toán tách rời: minimize sum(|xi - u|) + sum(|yi - v|) tương đương với minimize độc lập sum(|xi - u|) và sum(|yi - v|).
• Trung vị (Median) là điểm tối ưu để minimize tổng khoảng cách absolutes.
• Vì tọa độ đầu vào là số nguyên, ta có thể lấy giá trị trung vị ngay trên mảng đã sort mà không cần quan tâm quá nhiều đến các giá trị thực giữa các số nguyên.

Lỗi thường gặp

• Sử dụng trung bình cộng (Mean) thay vì trung vị (Median): Trung bình cộng minimize tổng bình phương khoảng cách (L2 norm), trong khi bài toán dùng Manhattan distance (L1 norm).
• Lỗi integer overflow: Tổng khoảng cách có thể lên tới ~N * 10^9 (với N=10^5), cần dùng kiểu dữ liệu 64-bit (long long).
• Quên sort mảng tọa độ trước khi lấy giá trị ở vị trí giữa.