Hiểu bài toán

Bài toán yêu cầu tính độ dài t tổng của hai đoạn thẳng [a, b] và [c, d] trên trục số, nhưng chỉ tính mỗi phần tử (hoặc đơn vị độ dài) một lần duy nhất, ngay cả nếu hai đoạn chồng lấn lên nhau. Nói cách khác, cần tìm độ dài của tập hợp giao [a, b] ∪ [c, d].

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

Cách Quy hoạch động / Marking (Mảng đánh dấu)

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

void danh_dau(vector<int> &arr, int a, int b) {
    for (int i = a; i < b; i++) {
        arr[i] = 1;
    }
}

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    vector<int> arr(101, 0);
    danh_dau(arr, a, b);
    danh_dau(arr, c, d);
    int cnt = 0;
    for (int i = 0; i <= 100; i++) {
        if (arr[i]) {
            ++cnt;
        }
    }
    cout << cnt;
    return 0;
}

• Time Complexity: O(W)
• Space Complexity: O(W)

Sử dụng một mảng boolean (hoặc mảng số nguyên) có kích thước足够 lớn (ví dụ 101) để biểu diễn các đơn vị trên tường. Duyệt qua đoạn [a, b] đánh dấu các vị trí đã sơn. Tiếp theo, duyệt đoạn [c, d] đánh dấu các vị trí đã sơn. Cuối cùng, đếm số lượng phần tử được đánh dấu. W là độ dài максималь của bức tường (100).

Cách Công thức toán học (Geometry)

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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int len1 = b - a;
    int len2 = d - c;
    int overlap = max(0, min(b, d) - max(a, c));
    int result = len1 + len2 - overlap;
    cout << result;
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đoạn [a, b] có độ dài (b - a). Đoạn [c, d] có độ dài (d - c). Nếu hai đoạn có giao nhau, độ dài phần giao là max(0, min(b, d) - max(a, c)). Để tính độ dài t tổng hợp lại, ta lấy tổng độ dài hai đoạn trừ đi độ dài phần giao (tránh đếm trùng). Công thức: (b - a) + (d - c) - overlap.

Cách Sắp xếp các điểm đầu mút

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

int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    vector<int> points = {a, b, c, d};
    sort(points.begin(), points.end());
    // points[0] < points[1] < points[2] < points[3]
    // Đoạn [a, b] bao gồm points[0] và points[1] hoặc points[2] và points[3]
    // Đoạn [c, d] bao gồm 2 điểm còn lại
    int ans = 0;
    ans += points[1] - points[0]; // Khoảng cách từ điểm nhỏ nhất đến điểm thứ 2
    ans += points[3] - points[2]; // Khoảng cách từ điểm thứ 3 đến điểm lớn nhất
    if (points[1] < points[2]) {
        // Nếu có khoảng trống giữa điểm thứ 2 và thứ 3, cộng thêm
        ans += points[2] - points[1];
    }
    cout << ans;
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Gom tất cả 4 điểm đầu mút (a, b, c, d) vào một mảng và sắp xếp tăng dần. Giả sử thứ tự là p0, p1, p2, p3. Hai đoạn [a, b] và [c, d] sẽ che phủ các khoảng [p0, p1] và [p2, p3] hoặc [p0, p2] và [p1, p3]. Tuy nhiên, với 4 điểm, tổng độ dài bao phủ luôn là (p1 - p0) + (p3 - p2) cộng thêm (p2 - p1) nếu p1 < p2 (tức là hai đoạn không chồng lấn). Nếu p1 >= p2, tức là chúng giao nhau, thì p2 - p1 <= 0 nên công thức tổng quát (p1 - p0) + (p3 - p2) + max(0, p2 - p1) vẫn đúng.

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

Bài học kinh nghiệm

• Bài toán về cơ bản là tìm độ dài tập hợp giao của hai đoạn thẳng.
• Có thể giải quyết bằng mô phỏng trực tiếp (đánh dấu) hoặc sử dụng công thức toán học dựa trên độ dài và điểm giao nhau.
• Công thức overlap = max(0, min(b, d) - max(a, c)) là chìa khóa để giải quyết bài toán một cách tối ưu.

Lỗi thường gặp

• Lầm tưởng rằng độ dài tổng bằng (b - a) + (d - c) mà không trừ đi phần chồng lấn.
• Khi sử dụng mảng đánh dấu, cần đảm bảo mảng có kích thước đủ lớn để chứa chỉ số lớn nhất (ví dụ b hoặc d có thể lên tới 100, nhưng b là tọa độ kết thúc, vòng lặp i < b nên mảng cần size > 100, hoặc dùng i <= b nếu coi là đánh dấu từng điểm).
• Sai lệch khi tính toán giao nhau nếu các đoạn không giao nhau (overlap < 0). Phải dùng max(0, ...).