Mục Lục

• Mô Tả Bài Toán
• Chiến Lược Giải Quyết
  • Giải Pháp Một
  • Giải Pháp Hai
• Mã Tham Khảo
  • Giải Pháp Một
  • Giải Pháp Hai

Mô Tả Bài Toán

Trong quá trình cải cách đất đai, H là một đảng viên ưu tú cần giúp người dân trong làng A phân phối lại đất đai. Làng A có đất rất dài và hẹp, có thể coi như một trục số. Mỗi hộ gia đình sở hữu một đoạn trên trục số từ \(A_i\) đến \(B_i\). Các đoạn này không bị lồng nhau hoàn toàn nhưng có thể chồng chéo. Yêu cầu là mỗi hộ gia đình phải nhận được một đoạn đất mới nằm trong đoạn đất cũ của họ và các đoạn đất không giao nhau. Hãy tìm chiều dài lớn nhất có thể của đoạn đất sao cho tất cả các hộ đều hài lòng. Kết quả trả về dưới dạng \(\frac{p}{q}\) với sai số nhỏ hơn \(10^{-6}\). Mỗi test case có \(T\) bộ dữ liệu. Với \(100\%\) dữ liệu: \(1 \leq T \leq 4\), \(1 \leq N \leq 10^5\), \(1 \leq A_i, B_i \leq 10^9\).

Chiến Lược Giải Quyết

Giải Pháp Một

Sử dụng phương pháp nhị phân để tìm kiếm giá trị gần đúng. Nếu một độ dài \(x\) hợp lệ thì mọi độ dài nhỏ hơn \(x\) cũng hợp lệ. Ta sử dụng hàm `check` để xác định xem một độ dài trung bình có hợp lệ hay không. Sau khi sắp xếp các đoạn theo thứ tự tăng dần, ta duyệt qua từng đoạn và kiểm tra khả năng phân phối.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Interval {
    int start, end;
};

bool compare(const Interval &a, const Interval &b) {
    if (a.start != b.start) return a.start < b.start;
    return a.end < b.end;
}

double check(double mid, vector<Interval>& intervals) {
    double current = intervals[0].start;
    for (auto &interval : intervals) {
        current = max(current, (double)interval.start);
        if (current + mid > interval.end) return false;
        current += mid;
    }
    return true;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<Interval> intervals(n);
        for (int i = 0; i < n; ++i) cin >> intervals[i].start >> intervals[i].end;
        sort(intervals.begin(), intervals.end(), compare);
        
        double left = 0, right = 1e9 + 7;
        while (right - left > 1e-10) {
            double mid = (left + right) / 2;
            if (check(mid, intervals)) left = mid;
            else right = mid;
        }
        cout << left << endl;
    }
    return 0;
}

Giải Pháp Hai

Đặt công thức tính giá trị tối thiểu giữa hai điểm trên trục số. Sử dụng khái niệm đường chéo để giải quyết bài toán bằng cách xây dựng vỏ lồi và tìm kiếm nhị phân kết quả.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Point {
    long long x, y;
};

long long gcd(long long a, long long b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<Point> points(n);
        for (int i = 0; i < n; ++i) cin >> points[i].x >> points[i].y;
        sort(points.begin(), points.end(), [](const Point &a, const Point &b) { return a.x < b.x; });
        
        long long ans_p = LLONG_MAX, ans_q = 1;
        vector<int> stack;
        for (int i = 0; i < n; ++i) {
            while (stack.size() >= 2) {
                int j = stack[stack.size() - 1], k = stack[stack.size() - 2];
                if ((points[j].x - points[k].x) * (i - j) < (points[i].x - points[j].x) * (j - k))
                    stack.pop_back();
                else break;
            }
            stack.push_back(i);
            int l = 1, r = stack.size() - 1;
            while (l < r) {
                int m = (l + r + 1) / 2;
                if ((points[i].y - points[stack[m]].x) * (stack[m] - stack[m - 1]) <= (points[stack[m]].x - points[stack[m - 1]].x) * (i - stack[m]))
                    l = m;
                else r = m - 1;
            }
            if ((points[i].y - points[stack[l]].x) * ans_q < (i - stack[l]) * ans_p)
                ans_p = points[i].y - points[stack[l]].x, ans_q = i - stack[l];
        }
        long long g = gcd(ans_p, ans_q);
        cout << ans_p / g << "/" << ans_q / g << "\n";
    }
    return 0;
}