Hướng dẫn giải của Thám hiểm

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, phantkhanh07, ynhi1403, nhkhanh236

Hiểu bài toán

Bài toán yêu cầu tìm chi phí nhiên liệu tối thiểu để di chuyển đến các điểm đến. Có n điểm hạ cánh, mỗi điểm có vị trí a[i] và chi phí nhiên liệu b[i] để đi từ điểm đó. Có m điểm đích cần đến, mỗi điểm có vị trí D[j]. Chi phí di chuyển từ một điểm hạ cánh a đến một điểm đích D là: |D - a| * c + b, trong đó c là hằng số.

Đối với mỗi điểm đích D[j], ta cần tìm giá trị nhỏ nhất của |D[j] - a[i]| * c + b[i] trong tất cả các điểm hạ cánh i (1 ≤ i ≤ n).

Dữ liệu:

  • 1 ≤ n, m ≤ 200,000
  • 1 ≤ a[i], D[j] ≤ 10^12
  • 1 ≤ b[i] ≤ 10^9
  • 1 ≤ c ≤ 10^9

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

Cách Brute Force
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // freopen("EXPFUEL.inp", "r", stdin);
    // freopen("EXPFUEL.out", "w", stdout);

    int n, m;
    long long c;
    cin >> n >> m >> c;

    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }

    vector<long long> d(m);
    for (int i = 0; i < m; i++) {
        cin >> d[i];
    }

    for (int j = 0; j < m; j++) {
        long long min_cost = LLONG_MAX;
        for (int i = 0; i < n; i++) {
            long long cost = abs(d[j] - a[i]) * c + b[i];
            if (cost < min_cost) {
                min_cost = cost;
            }
        }
        cout << min_cost << "\n";
    }

    return 0;
}
  • Time Complexity: O(n * m)
  • Space Complexity: O(n + m)

Với mỗi điểm đích D[j], duyệt qua tất cả các điểm hạ cánh a[i] để tính chi phí và lấy giá trị nhỏ nhất.

Độ phức tạp: O(n * m) vì với mỗi m điểm đích, ta duyệt qua n điểm hạ cánh. Với n, m ≤ 200,000, độ phức tạp này là ~4 * 10^10, quá lớn so với giới hạn thời gian.

Phương pháp này chỉ khả thi cho các test case nhỏ (n, m ≤ 5000).

Cách Binary Search + Prefix/Suffix Minimum
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
long long a[MAXN], b[MAXN], d[MAXN];
pair<long long, long long> points[MAXN];
long long pref[MAXN], suff[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // freopen("EXPFUEL.inp", "r", stdin);
    // freopen("EXPFUEL.out", "w", stdout);

    int n, m;
    long long c;
    cin >> n >> m >> c;

    for (int i = 1; i <= n; i++) {
        cin >> points[i].first >> points[i].second;
    }

    // Sort points by location
    sort(points + 1, points + n + 1);

    for (int i = 1; i <= m; i++) {
        cin >> d[i];
    }

    // Precompute prefix minimums for left side
    // pref[i] = min(b[k] - c * a[k]) for k in [1, i]
    pref[0] = LLONG_MAX;
    for (int i = 1; i <= n; i++) {
        long long val = points[i].second - c * points[i].first;
        if (i == 1) pref[i] = val;
        else pref[i] = min(pref[i-1], val);
    }

    // Precompute suffix minimums for right side
    // suff[i] = min(b[k] + c * a[k]) for k in [i, n]
    suff[n+1] = LLONG_MAX;
    for (int i = n; i >= 1; i--) {
        long long val = points[i].second + c * points[i].first;
        if (i == n) suff[i] = val;
        else suff[i] = min(suff[i+1], val);
    }

    for (int j = 1; j <= m; j++) {
        // Find position using binary search
        int pos = upper_bound(points + 1, points + n + 1, make_pair(d[j], LLONG_MAX)) - points - 1;

        long long ans = LLONG_MAX;

        // Consider point at pos (if exists)
        if (pos >= 1 && pos <= n) {
            ans = min(ans, abs(points[pos].first - d[j]) * c + points[pos].second);
        }
        // Consider point at pos + 1 (if exists)
        if (pos + 1 <= n) {
            ans = min(ans, abs(points[pos+1].first - d[j]) * c + points[pos+1].second);
        }

        // Use precomputed values
        // If D is to the right of all points (pos == n), only right formula applies
        // If D is to the left of all points (pos == 0), only left formula applies

        if (pos >= 1) {
            // D is to the right of point at pos
            // For points <= D, cost = c*D + (b - c*a)
            ans = min(ans, c * d[j] + pref[pos]);
        }
        if (pos + 1 <= n) {
            // D is to the left of point at pos+1
            // For points >= D, cost = -c*D + (b + c*a)
            ans = min(ans, -c * d[j] + suff[pos+1]);
        }

        cout << ans << "\n";
    }

    return 0;
}
  • Time Complexity: O((n + m) log n)
  • Space Complexity: O(n + m)

Phân tích chi phí: |D - a| * c + b.

Trường hợp 1: a ≤ D. Khi đó |D - a| = D - a. Chi phí = (D - a) * c + b = cD + (b - ca). Trường hợp 2: a > D. Khi đó |D - a| = a - D. Chi phí = (a - D) * c + b = -cD + (b + ca).

Ta có thể tối ưu hóa bằng cách:

  1. Sắp xếp các điểm hạ cánh theo vị trí.
  2. Với mỗi điểm đích D, dùng binary search để tìm vị trí pos sao cho a[pos] ≤ D < a[pos+1].
  3. Precompute:
    • pref[i] = min(b[k] - ca[k]) for k in [1, i] (dùng cho điểm hạ cánh nằm bên trái hoặc đúng D)
    • suff[i] = min(b[k] + ca[k]) for k in [i, n] (dùng cho điểm hạ cánh nằm bên phải D)

Với mỗi D, ta chỉ cần xét:

  • Chi phí từ các điểm a ≤ D: c*D + pref[pos]
  • Chi phí từ các điểm a > D: -c*D + suff[pos+1]

Độ phức tạp: O(n log n) để sort + O(m log n) để binary search cho mỗi điểm đích.

Cách Segment Tree / RMQ Optimization
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
const long long INF = 1e18;

struct Point {
    long long a, b;
    bool operator<(const Point& other) const {
        return a < other.a;
    }
};

struct Node {
    long long min_left, min_right; // min(b - c*a) and min(b + c*a)
    Node() : min_left(INF), min_right(INF) {}
};

Point points[MAXN];
long long d[MAXN];
Node tree[4 * MAXN];

Node merge(const Node& left, const Node& right) {
    Node res;
    res.min_left = min(left.min_left, right.min_left);
    res.min_right = min(left.min_right, right.min_right);
    return res;
}

void build(int node, int start, int end, long long c) {
    if (start == end) {
        tree[node].min_left = points[start].b - c * points[start].a;
        tree[node].min_right = points[start].b + c * points[start].a;
    } else {
        int mid = (start + end) / 2;
        build(2 * node, start, mid, c);
        build(2 * node + 1, mid + 1, end, c);
        tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
    }
}

Node query(int node, int start, int end, int l, int r) {
    if (r < start || end < l) return Node();
    if (l <= start && end <= r) return tree[node];
    int mid = (start + end) / 2;
    Node p1 = query(2 * node, start, mid, l, r);
    Node p2 = query(2 * node + 1, mid + 1, end, l, r);
    return merge(p1, p2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    // freopen("EXPFUEL.inp", "r", stdin);
    // freopen("EXPFUEL.out", "w", stdout);

    int n, m;
    long long c;
    cin >> n >> m >> c;

    for (int i = 1; i <= n; i++) {
        cin >> points[i].a >> points[i].b;
    }

    sort(points + 1, points + n + 1);

    for (int i = 1; i <= m; i++) {
        cin >> d[i];
    }

    build(1, 1, n, c);

    for (int j = 1; j <= m; j++) {
        // Find position using binary search
        int pos = upper_bound(points + 1, points + n + 1, Point{d[j], 0}) - points - 1;

        long long ans = INF;

        // Query for points <= D (left side)
        if (pos >= 1) {
            Node left_res = query(1, 1, n, 1, pos);
            ans = min(ans, c * d[j] + left_res.min_left);
        }

        // Query for points > D (right side)
        if (pos + 1 <= n) {
            Node right_res = query(1, 1, n, pos + 1, n);
            ans = min(ans, -c * d[j] + right_res.min_right);
        }

        cout << ans << "\n";
    }

    return 0;
}
  • Time Complexity: O((n + m) log n)
  • Space Complexity: O(n)

Cách tiếp cận này tương tự như Solution 2 nhưng thay vì dùng prefix/suffix arrays, ta dùng Segment Tree để query range minimum.

Các bước:

  1. Sắp xếp điểm hạ cánh theo vị trí.
  2. Xây dựng Segment Tree:
    • Mỗi node lưu min(b - ca) và min(b + ca) trong đoạn được quản lý.
  3. Với mỗi điểm đích D:
    • Dùng binary search để tìm pos (vị trí cuối cùng có a ≤ D)
    • Query Segment Tree từ 1 đến pos để lấy min(b - ca)
    • Query Segment Tree từ pos+1 đến n để lấy min(b + ca)
    • Tính chi phí và so sánh

Ưu điểm: Dễ dàng update thêm điểm hạ cánh mới nếu cần (dynamic).

Độ phức tạp: O(n log n) để build tree + O(m log n) để query.

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

Cách tiếp cận Time Space Tên
1 O(n * m) O(n + m) Brute Force
2 O((n + m) log n) O(n + m) Binary Search + Prefix/Suffix Minimum
3 O((n + m) log n) O(n) Segment Tree / RMQ Optimization

Bài học kinh nghiệm

  • Bài toán có thể biến đổi thành 2 trường hợp: D ≥ a và D < a, từ đó phân tích công thức để tách phần phụ thuộc D
  • Sử dụng sorting + binary search để giảm độ phức tạp từ O(n*m) xuống O((n+m)log n)
  • Precompute prefix/suffix minimum cho phép tính toán O(1) sau khi xác định vị trí

Lỗi thường gặp

  • Sử dụng sai kiểu dữ liệu (cần long long vì giá trị có thể lên tới 10^18)
  • Lỗi index mảng khi sort (nên bắt đầu từ 1 hoặc 0 nhất quán)
  • Quên xử lý biên khi điểm đích nằm ngoài khoảng [min(a), max(a)]

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.