Đoạn Phủ (DOANP)
Đề bài
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)$. Cần chọn ra một số đoạn để phủ hoàn toàn đoạn $[a, b]$. Hỏi số đoạn cần chọn ít nhất là bao nhiêu.
Dữ liệu nhập: gồm các dòng sau
- Dòng thứ nhất là 3 số nguyên $n, a, b$ cách nhau một khoảng trắng $(1 \le n \le 10^5$, $0 \le a < b \le 10^9)$.
- 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 10^9)$.
Dữ liệu xuất:
- Nếu có cách chọn các đoạn phủ, in ra số nguyên $m$ là số lượng đoạn ít nhất. Trong dòng tiếp theo in ra $m$ số nguyên là chỉ số của các đoạn được chọn, mỗi số cách nhau một khoảng trắng. Nếu có nhiều cách chọn, in ra một cách bất kỳ.
- Nếu không có cách chọn để phủ hết, in ra $-1$.
3 1 5
1 3
2 4
3 52
1 32 1 5
0 2
3 5-1
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 😇.
Link này công khai, bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên NTUCoderLộ trình lời giải, bấm vào từng phần để nhảy tới:
Ước lượngNhìn giới hạn đoán độ phức tạp
Khi nhìn vào bài có giới hạn $N$ tối đa $10^5$, các bạn có thể nhẩm tính: muốn chạy kịp 1 giây thì toàn bộ bài làm phải có độ phức tạp $O(N \log N)$ trở xuống. Nếu $O(N^2)$ (phép ^ ở đây là luỹ thừa chứ không phải phép xor bit nha) trở lên thì chắc chắn TLE, vì $N^2 = 10^{10}$ quá giới hạn $10^8$. Còn $N \log N \approx 17 \cdot 10^5$ thì yên tâm, nếu được $O(N)$ thì quá tốt.
Tham lamÝ tưởng: luôn chọn đoạn vươn xa nhất
Bài này dùng phương pháp tham lam (greedy). Tham lam nghĩa là ở mỗi bước ta chọn cách giải quyết tốt nhất trong các lựa chọn hiện tại, rồi cứ thế đi tiếp theo hướng tốt nhất. Không có công thức từng bước cụ thể như các thuật toán khác, miễn tư tưởng luôn là chọn theo hướng tốt nhất. Đọc đề thấy "đáp án phải nhỏ nhất/lớn nhất" là thấy mùi tham lam ngay 😄. Tham lam chỉ là tư tưởng, để hiện thực được nó có thể cần thêm các kỹ thuật bổ trợ khác, như trong chính bài này.
- Sắp xếp các đoạn thẳng tăng dần theo điểm bắt đầu (điểm kết thúc không quan tâm) để tạo quy luật cho các đoạn trên trục số. Phải dùng thuật toán sắp xếp $O(N \log N)$, dùng loại $O(N^2)$ sẽ TLE.
- Bắt đầu xét vị trí $A$: tìm tất cả các đoạn có điểm bắt đầu (start) $\le A$. Không xét các đoạn có start $> A$, vì như vậy đoạn đó đã không chứa điểm $A$.
- Trong số các đoạn có start $\le A$, tham lam chọn đoạn có điểm kết thúc (finish) lớn nhất để nó dài nhất, phủ được nhiều nhất. Đưa ID ban đầu của đoạn đó (theo thứ tự input) vào mảng
res, lưu finish đó vào biếnyMax. - Coi như đoạn từ $A$ đến
yMaxđã được phủ, lặp lại quy trình: tìm đoạn vươn xa nhất trong các đoạn có start $\le$yMax(không xét lại những đoạn đã xét). - Dừng khi đoạn tìm được có finish $\ge B$: in ra danh sách ID. Nếu chưa phủ hết mà không tìm ra đoạn nào có start $\le$ vị trí đang cần phủ thì kết luận $-1$.
Để tìm nhanh các đoạn có start $\le A$, ta dùng upper_bound tìm vị trí idx của đoạn đầu tiên có start $> A$ (danh sách đã sắp xếp tăng dần theo start). Các đoạn từ index $j$ đến idx − 1 là các ứng viên. Lần tìm sau bắt đầu từ idx trở đi, nên mỗi đoạn chỉ được xét đúng một lần.
Minh hoạChạy tay từng bước
Em nhập $a$, $b$ và danh sách các đoạn dạng s d cách nhau bởi dấu phẩy (tối đa 10 đoạn, toạ độ từ 0 đến 30), rồi bấm Tiếp:
CodeSource code
Nói mô tả ý tưởng thì sợ hơi khó hiểu, các bạn xem source code dưới đây hoạt động theo đúng ý tưởng mình đã trình bày ở trên nhé:
#include <bits/stdc++.h>
using namespace std;
struct Data{
int x, y, id;
};
bool cmp(const Data &a, const Data &b){
return a.x < b.x;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, x, y;
cin >> n >> x >> y;
Data a[n];
for(int i = 0; i < n; ++i){
cin >> a[i].x >> a[i].y;
a[i].id = i + 1;
}
sort(a, a + n, cmp);
vector<int> res;
bool check = false;
int yMax = a[0].y, idMax = a[0].id, j = 0;
while(check == false){
int idx = upper_bound(a + j, a + n, Data{x}, cmp) - a;
bool check2 = false;
for(int i = j; i < idx; ++i){
if(a[i].id != 0){
check2 = true;
if(a[i].y > yMax){
yMax = a[i].y;
idMax = a[i].id;
}
a[i].id = 0;
}
}
if(check2 == false){
break;
}
res.push_back(idMax);
if(yMax >= y){
check = true;
break;
}
else{
x = yMax;
j = idx;
}
}
if(check == false){
cout << -1;
}
else{
cout << res.size() << endl;
for(int i = 0; i < res.size(); ++i){
cout << res[i] << " ";
}
}
return 0;
}from bisect import bisect_right
class Data:
def __init__(self, x, y, id):
self.x = x
self.y = y
self.id = id
def __lt__(self, other):
return self.x < other.x
n, x, y = map(int, input().split())
a = []
for i in range(n):
xi, yi = map(int, input().split())
a.append(Data(xi, yi, i + 1))
a.sort()
res = []
check = False
yMax = a[0].y
idMax = a[0].id
j = 0
while not check:
idx = bisect_right(a, Data(x, 0, 0), j)
check2 = False
for i in range(j, idx):
if a[i].id != 0:
check2 = True
if a[i].y > yMax:
yMax = a[i].y
idMax = a[i].id
a[i].id = 0
if not check2:
break
res.append(idMax)
if yMax >= y:
check = True
break
else:
x = yMax
j = idx
if not check:
print(-1)
else:
print(len(res))
print(*res)Giải thích một số chỗ trong code
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 đang code theo ngôn ngữ 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é), nên kinh nghiệm trong các bài cần nhập xuất nhiều, như bài này phần input có thể lên đến $2 \cdot 10^5$ số, ta nên để thêm 2 dòng này vào đầu để chương trình chạy nhanh hơn. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.- Các đoạn thẳng cần 2 thông tin là start, finish nên mình tạo
struct Data, trong đó $x$ hiểu là start, $y$ hiểu là finish. Thêm thuộc tínhidlưu vị trí ban đầu của từng đoạn trong input, vì sau khi sắp xếp các đoạn đã bị xáo trộn, mà đề yêu cầu xuất ra id các đoạn được chọn. - Hàm
cmpchỉ ra so sánh giữa 2 cấu trúcDatadựa theo tiêu chí nào: ở đây so sánh $x$ (vị trí bắt đầu), sắp xếp tăng dần. sortvàupper_boundlà các hàm phổ biến, bạn nào chưa biết thì gõ tên hàm lên Google, mình khuyến khích xem các bài viết của GeeksforGeeks vì viết chi tiết, chất lượng. Do đang tìm trên mảng kiểu cấu trúc nên giá trị cần tìm cũng phải biến thành kiểuDatatương ứng:Data{x}có giá trị $x$ là giá trị cần tìm.- Vị trí bắt đầu tìm của
upper_boundvà vòng lặp sau đó làa + j: ban đầu $j = 0$ là tìm từ đầu mảng, các lần sau $j$ được cập nhật bằngidxcủa lần trước, thu hẹp phạm vi tìm để không tốn thêm độ phức tạp. check2là cờ hiệu cho biết có tìm ra đoạn nào phủ điểm đang cần phủ không. Nếu vẫnfalsethì thoát; ngược lại đưaidMaxvàores. Sau đó nếuyMax >= y(bài này mình dùng $x, y$ thay cho $A, B$) thì cập nhậtcheck = truevà thoát; nếu chưa thìx = yMax,j = idxđể lần sau tìm tiếp. Ra ngoài,checkvẫn làfalsethì in $-1$, ngược lại in mảngres.- Thuộc tính
idcòn được tận dụng làm cờ đánh dấu đoạn đã xét: ban đầu id tính từ 1 (luôn khác 0), xét xong đoạn nào thì gán id của nó bằng 0, về sau gặp id bằng 0 thì bỏ qua.
Không gian: mảng $N$ cấu trúc, mỗi cấu trúc 3 thành phần nên chính xác là $O(3N)$, theo quy tắc nhân BigO bỏ hằng số thì là $O(N)$. Thời gian: $O(N)$ đọc input, $O(N \log N)$ sắp xếp, bước xử lý mỗi đoạn chỉ xét một lần cộng các lần upper_bound. Theo quy tắc cộng BigO lấy thành phần lớn nhất là $O(N \log N)$, đến từ bước sắp xếp, nên yên tâm không bị TLE.
Mình đã kiểm tra cả 2 bản code với 500 bộ test ngẫu nhiên: số đoạn in ra luôn đúng bằng số đoạn ít nhất tìm bằng vét cạn, và các đoạn được chọn phủ kín đoạn $[a, b]$.
Nhận xét
Đăng nhận xét