Chiều dài phủ (DOANP2)

Nguồn: NTUCoder (DOANP2) Độ khó: Trung bình Sắp xếp Gộp đoạn

Đề bài

DOANP2 – Chiều dài phủ
Giới hạn thời gian: 1.0 giây · Giới hạn bộ nhớ: 128 megabyte

Trên trục số cho $n$ đoạn thẳng $[s_i, d_i]$, $s_i$ là điểm đầu và $d_i$ là điểm cuối ($s_i < d_i$ với $1 \le i \le n$). Hỏi tổng chiều dài được phủ bởi các đoạn trên là bao nhiêu.

Ví dụ cho 3 đoạn $[1,3]$, $[2,4]$ và $[3,5]$ như hình dưới thì tổng chiều dài phủ là 4.

Dữ liệu nhập: gồm các dòng sau

• Dòng thứ nhất là số nguyên $n$ ($1 \le n \le 10^5$) là số lượng các đoạn.
• Trong $n$ dòng tiếp theo, dòng thứ $i$ là hai số nguyên $s_i, d_i$ cách nhau một khoảng trắng ($0 \le s_i < d_i \le 2 \times 10^9$).

Dữ liệu xuất: Tổng chiều dài được phủ bởi các đoạn trên.

Ví dụ 1 – input

3
1 3
2 4
3 5

Ví dụ 1 – output

4

Ví dụ 2 – input

2
5 8
2 4

Ví dụ 2 – output

5

Lời mở đầu

Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇. Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Chuẩn bịGiới hạnCách 1Tô đoạn đơn vịÝ tưởngSắp xếp, gộpCách 2O(N log N)

Chuẩn bịNhìn giới hạn đoán độ phức tạp

Khi nhìn vào bài mà có giới hạn $N$ tối đa $10^5$ thì các bạn có thể nhẩm tính chắc chắn muốn chạy trong giới hạn 1 giây thì toàn bộ bài làm phải có độ phức tạp thời gian là $O(N \log N)$ trở xuống, chứ nếu mà $O(N^2)$ trở lên thì chắc chắn là sẽ bị TLE. Vì $N = 10^5$ thì $N^2 = 10^{10}$ là quá ngưỡng $10^8$ rồi. Còn $N \log N \approx 17 \cdot 10^5$ thì ít hơn ngưỡng $10^8$ nhiều nên yên tâm không bị TLE, hoặc nếu có thể độ phức tạp ít hơn nữa ví dụ $O(N)$ thì quá tốt.

Ngoài ra bài này còn một giới hạn nữa cần để ý: tọa độ lên tới $2 \times 10^9$. Nên nhìn vào 1 bài ta nhìn ngay các giới hạn độ lớn mà ước tính thuật toán phải có độ phức tạp bao nhiêu, từ đó sẽ định hình ra cách giải quyết.

Cách 1Vét cạn: tô từng đoạn đơn vị

Cách dễ nghĩ nhất: chia trục số thành các đoạn đơn vị $[x, x+1]$. Mỗi đoạn $[s, d]$ sẽ phủ đúng các đoạn đơn vị $[s, s+1],$ $[s+1, s+2],$ $\dots,$ $[d-1, d]$, tức là $x$ chạy từ $s$ đến $d - 1$. Ta dùng mảng đánh dấu phu[x] = true nghĩa là đoạn đơn vị $[x, x+1]$ đã được phủ. Đọc hết các đoạn và tô xong thì đếm số ô được tô – đó chính là tổng chiều dài phủ. Ô nào bị nhiều đoạn chồng lên cũng chỉ tính 1 lần nên không sợ bị đếm trùng.

Ví dụ đề: $[1,3]$ tô ô 1, 2; $[2,4]$ tô ô 2, 3; $[3,5]$ tô ô 3, 4. Các ô được tô là 1, 2, 3, 4 → chiều dài phủ là 4.

Code dưới đây chỉ dùng được khi tọa độ nhỏ (ở đây mình cho tối đa 1000) để các bạn hiểu ý tưởng:

Code cách 1 – vét cạn tô đoạn đơn vị (chỉ cho tọa độ ≤ 1000)

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

int main(){
    int n;
    cin >> n;
    vector<bool> phu(1001, false);   // phu[x] = true: đoạn đơn vị [x, x+1] đã được phủ
    int maxD = 0;
    for(int i = 0; i < n; ++i){
        int s, d;
        cin >> s >> d;
        maxD = max(maxD, d);
        for(int x = s; x < d; ++x){
            phu[x] = true;
        }
    }
    int res = 0;
    for(int x = 0; x < maxD; ++x){
        if(phu[x]){
            res++;
        }
    }
    cout << res;
    return 0;
}

n = int(input())
phu = [False] * 1001   # phu[x] = True: đoạn đơn vị [x, x+1] đã được phủ
for _ in range(n):
    s, d = map(int, input().split())
    for x in range(s, d):
        phu[x] = True
print(sum(phu))

C++▶ Chạy tay từng dòng codeCách 1: tô từng đoạn đơn vị [x, x+1] rồi đếm số ô đã tô (chỉ cho tọa độ nhỏ).

Dữ liệu vào (stdin) – sửa thoải mái3 1 3 2 4 3 5

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 int n;

6 cin >> n;

7 vector<bool> phu(1001, false); // phu[x] = true: đoạn đơn vị [x, x+1] đã được phủ

8 int maxD = 0;

9 for(int i = 0; i < n; ++i){

10 int s, d;

11 cin >> s >> d;

12 maxD = max(maxD, d);

13 for(int x = s; x < d; ++x){

14 phu[x] = true;

15 }

16 }

17 int res = 0;

18 for(int x = 0; x < maxD; ++x){

19 if(phu[x]){

20 res++;

21 }

22 }

23 cout << res;

24 return 0;

25}

ChậmVừaNhanhRất nhanh

Vì sao cách này không qua được bài?

Tọa độ lên tới $2 \times 10^9$ thì mảng đánh dấu phải có 2 tỷ ô – vượt xa 128 MB bộ nhớ. Chưa kể mỗi đoạn có thể dài tới $2 \times 10^9$, tô từng ô cho $10^5$ đoạn thì số lần lặp lên tới $2 \cdot 10^{14}$, chắc chắn TLE. Ta phải nghĩ cách không phụ thuộc vào độ lớn tọa độ.

Ý tưởngSắp xếp theo điểm đầu rồi gộp đoạn

Đầu tiên ta cần sắp xếp danh sách các đoạn thẳng tăng dần theo điểm bắt đầu, làm như thế để tạo quy luật cho các đoạn thẳng trên trục số: đoạn nào bắt đầu trước thì xét trước. Ở bước sắp xếp này như đã phân tích ở trên thì ta phải dùng thuật toán sắp xếp tối ưu $O(N \log N)$ (hàm sort có sẵn), chứ nếu dùng những thuật toán sắp xếp $O(N^2)$ thì sẽ bị TLE.

Sau khi sắp xếp, ta đi từ trái sang phải và luôn giữ một khối đang phủ $[L, R]$ (ban đầu chính là đoạn đầu tiên). Xét đoạn tiếp theo $[s, d]$:

• Nếu $s > R$: đoạn mới tách rời khối hiện tại (có khoảng trống ở giữa). Vì các đoạn sau đều có điểm đầu $\ge s > R$ nên không còn đoạn nào nối dài được khối cũ nữa → chốt khối cũ: cộng $R - L$ vào kết quả, rồi bắt đầu khối mới $[L, R] = [s, d]$.
• Ngược lại $s \le R$: đoạn mới chồng (hoặc chạm) lên khối hiện tại → gộp vào khối. Nếu $d > R$ thì khối được nối dài ra: $R = d$; còn nếu $d \le R$ thì đoạn mới nằm gọn trong khối, không thay đổi gì.

Xét hết các đoạn thì nhớ cộng nốt khối cuối cùng $R - L$ vào kết quả. Mỗi chỗ chồng lên nhau chỉ nằm trong đúng 1 khối nên không bị đếm trùng.

Các đoạn $[1,3], [2,4], [3,5]$ gộp thành khối $[1,5]$ dài 4; đoạn $[7,9]$ tách rời thành khối riêng dài 2 → tổng 6.

Tư tưởng tham lam

Mỗi bước ta chỉ cần nhớ khối đang phủ và đẩy đầu phải $R$ đi xa nhất có thể. Nhờ đã sắp xếp theo điểm đầu nên hễ gặp đoạn có $s > R$ là chắc chắn khối cũ đã xong, khỏi cần ngó lại.

Em nhập các đoạn rồi bấm Tiếp để xem từng bước gộp đoạn:

Các đoạn (s d; ...)

Ví dụ nhanh:

Cách 2Code sắp xếp + gộp đoạn – O(N log N)

Source code các bạn tham khảo để nhìn thấy rõ với tất cả những gì mình đã phân tích ở trên:

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<pair<int, int>> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end());
    long long res = 0;
    int L = a[0].first, R = a[0].second;
    for(int i = 1; i < n; ++i){
        if(a[i].first > R){
            res += R - L;
            L = a[i].first;
            R = a[i].second;
        }
        else if(a[i].second > R){
            R = a[i].second;
        }
    }
    res += R - L;
    cout << res;
    return 0;
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = sorted(zip(map(int, data[1:2 * n + 1:2]), map(int, data[2:2 * n + 2:2])))
    res = 0
    L, R = a[0]
    for s, d in a[1:]:
        if s > R:            # đoạn mới nằm tách rời: chốt khối cũ
            res += R - L
            L, R = s, d
        elif d > R:          # chồng lên khối cũ: nối dài khối
            R = d
    res += R - L
    print(res)

main()

C++▶ Chạy tay từng dòng codeCách 2: sắp xếp theo điểm đầu, giữ khối [L, R] đang phủ, gặp đoạn tách rời thì chốt khối – O(N log N).

Dữ liệu vào (stdin) – sửa thoải mái6 7 9 1 3 3 5 2 4 12 15 13 14

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 ios::sync_with_stdio(0);

6 cin.tie(0);

7 int n;

8 cin >> n;

9 vector<pair<int, int>> a(n);

10 for(int i = 0; i < n; ++i){

11 cin >> a[i].first >> a[i].second;

12 }

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

14 long long res = 0;

15 int L = a[0].first, R = a[0].second;

16 for(int i = 1; i < n; ++i){

17 if(a[i].first > R){

18 res += R - L;

19 L = a[i].first;

20 R = a[i].second;

21 }

22 else if(a[i].second > R){

23 R = a[i].second;

24 }

25 }

26 res += R - L;

27 cout << res;

28 return 0;

29}

ChậmVừaNhanhRất nhanh

Giải thích một số chỗ trong code ở trên:

1. ios::sync_with_stdio(0); cin.tie(0); 2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn code C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé). Bài này input có thể lên đến $2 \cdot 10^5$ số cần nhập nên ta thêm 2 dòng này cho chương trình chạy nhanh hơn.
2. Mỗi đoạn lưu bằng pair<int, int> với first là điểm đầu, second là điểm cuối. Hàm sort sắp xếp pair theo first trước nên ta không cần viết hàm so sánh riêng.
3. Kết quả res mình để kiểu long long cho an toàn. Thực ra tổng chiều dài phủ không vượt quá $2 \times 10^9$ (vẫn vừa kiểu int vì int chứa tối đa khoảng $2.147 \times 10^9$) nhưng sát nút quá, các bạn tập thói quen dùng long long cho các tổng là tốt nhất.
4. Đề cho $s_i < d_i$ và $n \ge 1$ nên luôn có ít nhất 1 đoạn, khởi tạo khối bằng a[0] là an toàn.

Đánh giá độ phức tạp của cách làm này:

Không gian$O(N)$

Thời gian$O(N \log N)$

$O(N)$ cho bước đọc dữ liệu, $O(N \log N)$ cho bước sắp xếp, $O(N)$ cho bước gộp đoạn. Theo quy tắc cộng BigO lấy thành phần lớn nhất nên tổng quát là $O(N \log N)$, đến từ bước sắp xếp. Với $N = 10^5$ thì chỉ khoảng $1.7 \cdot 10^6$ phép toán, yên tâm không bị TLE. Và độ phức tạp này không phụ thuộc vào độ lớn tọa độ, đó chính là điểm hơn hẳn cách 1.

Kết quả kiểm tra: cả 2 cách (C++ và Python) đã được chạy với 250 bộ test ngẫu nhiên (tọa độ nhỏ, có đoạn trùng, đoạn lồng nhau, đoạn chạm đầu mút), so với cách đếm bằng tập hợp các đoạn đơn vị – khớp hết. Với test lớn nhất ($n = 10^5$, tọa độ tới $2 \times 10^9$), code cách 2 bằng C++ chạy khoảng 0,04 giây, Python khoảng 0,3 giây; test $10^5$ đoạn đều là $[0, 2 \times 10^9]$ cho đúng kết quả $2\,000\,000\,000$.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇