Chuyên đề cơ bản 2: Sắp xếp, kỹ thuật sự kiện (sweep line) và nén số (rời rạc hoá) trong C++ và Python: gộp đoạn, khách nhà hàng, xếp phòng
Lời mở đầu
Trong đề HSG có cả một họ bài nói về các đoạn trên trục số: khách ra vào nhà hàng, cuộc họp chiếm phòng, đèn bật tắt theo giờ, sơn từng khúc hàng rào… Đề hỏi “lúc đông nhất có bao nhiêu người?”, “tổng chiều dài được sơn là bao nhiêu?”, “cần ít nhất mấy phòng?”. Nếu toạ độ nhỏ, em đã biết dùng mảng hiệu ở bài 13. Nhưng khi toạ độ lên tới $10^9$, mảng hiệu không khai báo nổi, và lúc đó sắp xếp trở thành chìa khoá.
Chuyên đề này giả sử em đã học bài 10: Struct và sắp xếp (hàm sort, sắp xếp pair, hàm so sánh), bài 16: Tìm kiếm nhị phân (lower_bound) và bài 18: Tham lam. Ta không học lại cách sắp xếp, mà học cách dùng sắp xếp để biến bài $O(n^2)$ thành $O(n \log n)$.
sort + unique + lower_bound, kết hợp với mảng hiệu; ứng dụng tìm điểm được phủ nhiều nhất và xếp phòng ít nhất bằng priority_queue. Có 2 khung chạy tay, 3 mô phỏng bấm từng bước và 8 bài tập kèm gợi ý.Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Sắp xếp để mở khoá lời giải
Nhiều bài hỏi về cặp phần tử: hai số gần nhau nhất, có bao nhiêu giá trị khác nhau, có hai số nào trùng không… Cách ngây thơ là hai vòng for xét mọi cặp, tốn $O(n^2)$: với $n = 2 \cdot 10^5$ là $2 \cdot 10^{10}$ phép so sánh, chạy cả phút. Sắp xếp trước, mọi thứ trở nên “có thứ tự”, và câu hỏi về cặp thường chỉ cần nhìn hai phần tử kề nhau.
Nhận xét 1: cặp gần nhau nhất là một cặp kề nhau. Giả sử dãy đã tăng $a_0 \le a_1 \le \ldots \le a_{n-1}$ và xét hai chỉ số $i < j$ không kề nhau. Khi đó $a_j - a_i = (a_j - a_{j-1}) + \ldots + (a_{i+1} - a_i)$ là tổng của nhiều hiệu kề nhau không âm, nên nó không nhỏ hơn hiệu kề $a_{i+1} - a_i$. Vậy chỉ cần xét $n - 1$ cặp kề nhau thay vì $\frac{n(n-1)}{2}$ cặp.
Nhận xét 2: các số bằng nhau đứng liền thành một cụm. Số giá trị khác nhau = 1 + số vị trí $i$ mà $a_i \ne a_{i-1}$. Kiểm tra trùng cũng chỉ cần so ô kề.
| Chỉ số | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Dãy gốc | 31 | 7 | 18 | 7 | 25 | 12 | 40 |
| Sau khi sắp xếp | 7 | 7 | 12 | 18 | 25 | 31 | 40 |
| Hiệu với ô trước | – | 0 | 5 | 6 | 7 | 6 | 9 |
| Giá trị mới? | có | trùng | có | có | có | có | có |
Bảng 1. Sau khi sắp xếp: hiệu kề nhỏ nhất là 0 (hai số 7), dãy có $1 + 5 = 6$ giá trị khác nhau. Chỉ cần một vòng for qua các ô kề.
Xem code C++ / Python: hiệu nhỏ nhất và số giá trị khác nhau sau khi sắp xếp (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for(auto &x : a) cin >> x;
sort(a.begin(), a.end());
long long best = LLONG_MAX;
int khac = 1;
for(int i = 1; i < n; i++){
best = min(best, a[i] - a[i - 1]); // chỉ cần so hai số KỀ nhau
if(a[i] != a[i - 1]) khac++; // gặp một giá trị mới
}
cout << best << "\n" << khac;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = sorted(map(int, data[1:n + 1]))
best = min(a[i] - a[i - 1] for i in range(1, n)) # chỉ cần so hai số KỀ nhau
khac = 1 + sum(1 for i in range(1, n) if a[i] != a[i - 1]) # gặp một giá trị mới
print(best)
print(khac)(giá trị, chỉ số) như bài 10 đã dạy:vector<pair<long long, int>> p(n);
for(int i = 0; i < n; i++) p[i] = {a[i], i};
sort(p.begin(), p.end()); // p[k].second là vị trí gốc của số nhỏ thứ korder = sorted(range(n), key=lambda i: a[i]). Đây cũng là bước đầu tiên của mọi bài “xếp lịch” ở phần 5: sắp xếp khách theo giờ đến nhưng vẫn nhớ khách nào là ai.Một vài “phản xạ sắp xếp” khác em nên có: đếm cặp có tổng $\le X$ (sắp xếp rồi dùng hai con trỏ), tìm số lần xuất hiện của $x$ (sắp xếp rồi upper_bound − lower_bound), chọn $k$ món rẻ nhất (sắp xếp rồi lấy $k$ món đầu). Còn từ phần 2 trở đi, ta sẽ sắp xếp những thứ phức tạp hơn một con số: các đoạn và các sự kiện.
Phần 2Gộp đoạn và tổng độ dài phủ
Bài toán. Cho $n$ đoạn $[l_i, r_i]$ trên trục số (toạ độ tới $10^9$). Tô màu tất cả các đoạn. Hỏi phần được tô gồm bao nhiêu khối rời nhau và tổng chiều dài là bao nhiêu? Cộng thẳng $\sum (r_i - l_i)$ sẽ sai, vì phần chồng nhau bị tính nhiều lần.
Ý tưởng. Sắp xếp các đoạn theo đầu trái $l$. Giữ một “khối đang gộp” $[L, R]$. Duyệt từng đoạn $[l, r]$ theo thứ tự đã sắp xếp:
- Nếu $l \le R$: đoạn này chồng hoặc chạm vào khối, nối dài khối: $R = \max(R, r)$.
- Nếu $l > R$: có một khe hở. Mọi đoạn phía sau còn có $l$ lớn hơn nữa, nên không đoạn nào lấp được khe này: chốt khối $[L, R]$ (cộng $R - L$ vào đáp án) rồi mở khối mới $[l, r]$.
Chính việc sắp xếp đảm bảo điều “không đoạn nào phía sau quay lại lấp khe được”. Nếu không sắp xếp, một đoạn ở cuối danh sách có thể nằm ngay giữa hai khối và nối chúng lại. Em xem mô phỏng bên dưới với 6 đoạn cho theo thứ tự lộn xộn:
| Đoạn (đã sắp xếp) | So với R | Việc làm | Khối [L, R] | Tổng đã chốt |
|---|---|---|---|---|
| [1, 3] | – | mở khối đầu | [1, 3] | 0 |
| [2, 5] | 2 ≤ 3 | nối dài, R = max(3, 5) | [1, 5] | 0 |
| [6, 9] | 6 > 5 | chốt [1, 5], mở khối mới | [6, 9] | 4 |
| [8, 10] | 8 ≤ 9 | nối dài, R = 10 | [6, 10] | 4 |
| [12, 15] | 12 > 10 | chốt [6, 10], mở khối mới | [12, 15] | 8 |
| [13, 14] | 13 ≤ 15 | nằm gọn trong khối, R = max(15, 14) = 15 | [12, 15] | 8 |
| (hết) | chốt khối cuối | 11 |
Bảng 2. Gộp 6 đoạn của mô phỏng: được 3 khối [1, 5], [6, 10], [12, 15], tổng độ dài $4 + 4 + 3 = 11$.
Code rất ngắn. Để ý dòng cuối sau vòng lặp: khối cuối cùng chưa bao giờ gặp “khe hở” nên phải tự chốt. Em bấm Tiếp để chạy tay:
Xem code C++ / Python: gộp đoạn và tổng độ dài phủ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<pair<long long, long long>> a(n);
for(auto &p : a) cin >> p.first >> p.second;
sort(a.begin(), a.end()); // theo đầu trái l
long long L = a[0].first, R = a[0].second, tong = 0;
int khoi = 1;
for(int i = 1; i < n; i++){
if(a[i].first <= R) R = max(R, a[i].second); // chồng hoặc chạm: nối dài khối
else {
tong += R - L; khoi++; // có khe hở: chốt khối cũ
L = a[i].first; R = a[i].second;
}
}
tong += R - L; // đừng quên khối cuối cùng
cout << khoi << " " << tong;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
seg = sorted((int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n)) # theo đầu trái l
L, R = seg[0]
tong, khoi = 0, 1
for l, r in seg[1:]:
if l <= R: # chồng hoặc chạm: nối dài khối
R = max(R, r)
else: # có khe hở: chốt khối cũ
tong += R - L
khoi += 1
L, R = l, r
tong += R - L # đừng quên khối cuối cùng
print(khoi, tong)R = r thay vì R = max(R, r): sai ngay khi có đoạn nằm gọn trong khối (như [13, 14] trong [12, 15]).2. Quên chốt khối cuối sau vòng lặp.
3. Nhầm điều kiện “chạm”. Với đoạn trên trục số thực, $[1, 3]$ và $[3, 5]$ chạm nhau ở điểm 3, gộp hay không gộp thì tổng độ dài vẫn đúng, chỉ khác số khối. Nhưng với đoạn số nguyên (các ô 1, 2, 3 và ô 4, 5) thì $[1, 3]$ và $[4, 5]$ liền nhau thành một khối 5 ô, điều kiện gộp phải là
l <= R + 1 và độ dài một khối là $R - L + 1$. Đọc đề kỹ xem đoạn là “khúc trên trục số” hay “dãy ô”.Phần 3Kỹ thuật sự kiện (sweep line)
Bài toán khách nhà hàng. Có $n$ đoạn $[l_i, r_i]$ (các điểm nguyên, toạ độ tới $10^9$). Hỏi có một điểm được nhiều đoạn phủ nhất là bao nhiêu đoạn? Đổi lời: khách $i$ ngồi ở nhà hàng từ phút $l_i$ tới hết phút $r_i$, lúc đông nhất có mấy khách?
Nếu toạ độ $\le 10^6$, em làm ngay bằng mảng hiệu: d[l]++, d[r + 1]--, cộng dồn rồi lấy max. Hãy nhìn kỹ mảng hiệu ấy: nó chỉ khác 0 tại $2n$ vị trí, còn lại toàn số 0 vô ích. Kỹ thuật sự kiện chính là mảng hiệu “chỉ lưu những ô khác 0”:
- Mỗi đoạn $[l, r]$ sinh ra 2 sự kiện: $(l, +1)$ “bắt đầu phủ” và $(r + 1, -1)$ “hết phủ”.
- Sắp xếp $2n$ sự kiện theo thời điểm.
- Cho một đường quét chạy từ trái sang phải qua các sự kiện, giữ biến
cur= số đoạn đang phủ đường quét: gặp $+1$ thì tăng, gặp $-1$ thì giảm. Đáp án là giá trị lớn nhất củacur.
Độ phức tạp $O(n \log n)$ cho bước sắp xếp, không phụ thuộc toạ độ lớn cỡ nào. Hình dưới là 5 đoạn của ví dụ, và cột ở dưới là số đoạn phủ mỗi điểm nguyên: cao nhất là 3.
Hình 1. Năm đoạn [1, 4], [2, 6], [5, 8], [7, 9], [3, 5]. Giữa hai sự kiện liên tiếp, số đoạn phủ không đổi, nên chỉ cần tính lại cur tại các sự kiện. Cột vàng: điểm được 3 đoạn phủ.
Em bấm Tự chạy để xem đường quét màu đỏ nhảy từ sự kiện này sang sự kiện khác. Hãy để ý thời điểm 5 và 7: có một đoạn kết thúc và một đoạn bắt đầu cùng lúc. Sau đó đổi sang chế độ “Khách rời lúc r” để thấy sự kiện $-1$ dời về đúng $r$:
Thứ tự sự kiện trùng thời điểm là chỗ quyết định đúng sai. Tại $t = 5$ có sự kiện $(5, -1)$ của đoạn [1, 4] và $(5, +1)$ của đoạn [5, 8]. Đoạn [1, 4] không phủ điểm 5, nên phải trừ nó trước rồi mới cộng [5, 8]. Khi sắp xếp cặp (t, d), C++ và Python so t trước, bằng nhau thì so d; vì $-1 < +1$ nên sự kiện kết thúc tự động đứng trước. Rất tiện!
| Thứ tự tại t = 5 | cur trước | Sau sự kiện thứ nhất | Sau sự kiện thứ hai | best |
|---|---|---|---|---|
| −1 trước, +1 sau (đúng) | 3 | 2 | 3 | 3 |
| +1 trước, −1 sau (sai) | 3 | 4 | 3 | 4 (sai) |
Bảng 3. Nếu xử lý +1 trước, có một khoảnh khắc “ảo” mà cả 4 đoạn được đếm cùng lúc, dù không điểm nào được 4 đoạn phủ.
Xem code C++ / Python: đếm số đoạn phủ cùng lúc nhiều nhất bằng sự kiện (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<pair<long long, int>> ev; // (thời điểm, +1 hoặc -1)
for(int i = 0; i < n; i++){
long long l, r;
cin >> l >> r;
ev.push_back({l, +1}); // đoạn bắt đầu phủ từ l
ev.push_back({r + 1, -1}); // hết phủ từ r + 1
}
sort(ev.begin(), ev.end()); // cùng thời điểm: -1 đứng trước +1
int cur = 0, best = 0;
for(auto e : ev){
cur += e.second;
best = max(best, cur);
}
cout << best;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
ev = [] # (thời điểm, +1 hoặc -1)
for i in range(n):
l, r = int(data[1 + 2 * i]), int(data[2 + 2 * i])
ev.append((l, 1)) # đoạn bắt đầu phủ từ l
ev.append((r + 1, -1)) # hết phủ từ r + 1
ev.sort() # cùng thời điểm: -1 đứng trước +1
cur = best = 0
for t, d in ev:
cur += d
best = max(best, cur)
print(best)Khách đến lúc $a$, rời lúc $b$, người rời lúc $b$ không gặp người đến lúc $b$ (nửa mở $[a, b)$): sự kiện $(a, +1)$, $(b, -1)$; trùng thời điểm thì $-1$ trước (sắp xếp cặp tự lo).
Chỉ cần chạm nhau ở đầu mút là tính gặp nhau (đoạn đóng trên trục số thực, toạ độ có thể là số thực): sự kiện đặt tại $l$ và $r$, nhưng trùng thời điểm thì bắt đầu phải trước kết thúc. Mẹo: lưu cặp
(l, 0) cho bắt đầu và (r, 1) cho kết thúc, vì $0 < 1$ nên sắp xếp tự đưa bắt đầu lên trước; khi quét, gặp 0 thì cur++, gặp 1 thì cur--.Luôn tự hỏi: “ở đúng thời điểm trùng, hai đoạn có được tính là cùng lúc không?”
Phần 4Nén số (rời rạc hoá)
Kỹ thuật sự kiện rất mạnh khi chỉ cần quét một lượt. Nhưng nhiều bài muốn dùng mảng đánh chỉ số theo giá trị: mảng đếm, mảng hiệu, cộng dồn, sau này là cây Fenwick… mà giá trị tới $10^9$ thì không thể khai báo mảng. Quan sát quan trọng: trong rất nhiều bài, ta chỉ quan tâm thứ tự lớn nhỏ của các giá trị, không quan tâm chính xác chúng bằng bao nhiêu. Khi đó có thể thay mỗi số bằng thứ hạng của nó trong các giá trị khác nhau. $n$ số thì có tối đa $n$ thứ hạng, mảng chỉ cần $n$ ô.
Ba bước nén, nhớ như một câu thần chú “sắp xếp, bỏ trùng, tra vị trí”:
- Chép dãy sang
brồisort(b). b.erase(unique(b.begin(), b.end()), b.end()):uniquedồn các phần tử không trùng ô kề lên đầu và trả về chỗ kết thúc,erasecắt phần thừa. Còn $m$ giá trị khác nhau tăng dần.- Chỉ số nén của $x$ là
lower_bound(b.begin(), b.end(), x) - b.begin(), tìm nhị phân $O(\log m)$.
Kết quả: mọi giá trị nằm trong $0 \ldots m - 1$ và giữ nguyên thứ tự: $a_i < a_j \Leftrightarrow c_i < c_j$. Muốn lấy lại giá trị gốc thì đọc b[c[i]].
Xem code C++ / Python: nén số bằng sort, unique, lower_bound (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for(auto &x : a) cin >> x;
vector<long long> b = a; // 1. chép
sort(b.begin(), b.end()); // 2. sắp xếp
b.erase(unique(b.begin(), b.end()), b.end()); // 3. bỏ trùng
for(int i = 0; i < n; i++){
int c = lower_bound(b.begin(), b.end(), a[i]) - b.begin(); // 4. tra vị trí
cout << c << " ";
}
cout << "\n" << b.size();
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
b = sorted(set(a)) # sắp xếp + bỏ trùng
idx = {v: i for i, v in enumerate(b)} # giá trị -> chỉ số nén
print(*[idx[x] for x in a])
print(len(b))sorted(set(a)) làm luôn bước 1 và 2, rồi tạo từ điển idx = {v: i for i, v in enumerate(b)} để tra $O(1)$ thay vì bisect_left. Trong C++ cũng có thể dùng map như vậy, nhưng lower_bound trên vector đã sắp xếp nhanh hơn map khá nhiều.Nén + mảng hiệu. Bài toán: cho $n$ đoạn $[l_i, r_i]$ và $q$ câu hỏi, mỗi câu hỏi điểm $x$ được bao nhiêu đoạn phủ (toạ độ tới $10^9$). Ý tưởng: mảng hiệu chỉ “chạm” vào các toạ độ $l_i$, $r_i + 1$, và ta chỉ hỏi tại các $x_j$. Gom tất cả các toạ độ đó lại rồi nén. Giữa hai toạ độ nén liên tiếp, số đoạn phủ không đổi, nên mảng hiệu trên chỉ số nén cho đúng đáp án tại mọi điểm cần hỏi. Đây là đúng mảng hiệu của bài 13, chỉ khác là chỉ số đã được nén.
| Toạ độ gốc | 1 | 3 | 4 | 5 | 6 | 1000000000 | 1000000001 |
|---|---|---|---|---|---|---|---|
| Đến từ | $l$ của [1, 5] | $l$ của [3, $10^9$] | $l$ của [4, 4] và câu hỏi $x = 4$ | $r + 1$ của [4, 4] | $r + 1$ của [1, 5], câu hỏi $x = 6$ | câu hỏi $x = 10^9$ | $r + 1$ của [3, $10^9$] |
| Chỉ số nén | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| Hiệu d | +1 | +1 | +1 | −1 | −1 | 0 | −1 |
| Cộng dồn = số đoạn phủ | 1 | 2 | 3 | 2 | 1 | 1 | 0 |
Bảng 4. Ba đoạn [1, 5], [3, 10^9], [4, 4] và các câu hỏi $x = 4, 6, 10^9$: mảng hiệu chỉ cần 7 ô thay vì $10^9$ ô.
Xem code C++ / Python: nén toạ độ kết hợp mảng hiệu để trả lời số đoạn phủ một điểm (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<long long> l(n), r(n), x(q), b;
for(int i = 0; i < n; i++){
cin >> l[i] >> r[i];
b.push_back(l[i]); b.push_back(r[i] + 1); // mọi toạ độ mảng hiệu sẽ chạm tới
}
for(int j = 0; j < q; j++){ cin >> x[j]; b.push_back(x[j]); }
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
auto id = [&](long long v){ return int(lower_bound(b.begin(), b.end(), v) - b.begin()); };
vector<int> d(b.size() + 1, 0);
for(int i = 0; i < n; i++){
d[id(l[i])]++; // mảng hiệu trên chỉ số đã nén
d[id(r[i] + 1)]--;
}
for(int k = 1; k < (int)b.size(); k++) d[k] += d[k - 1]; // cộng dồn
for(int j = 0; j < q; j++) cout << d[id(x[j])] << "\n";
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
seg = [(int(data[2 + 2 * i]), int(data[3 + 2 * i])) for i in range(n)]
xs = list(map(int, data[2 + 2 * n:2 + 2 * n + q]))
b = sorted(set([l for l, r in seg] + [r + 1 for l, r in seg] + xs))
idx = {v: i for i, v in enumerate(b)}
d = [0] * (len(b) + 1)
for l, r in seg:
d[idx[l]] += 1 # mảng hiệu trên chỉ số đã nén
d[idx[r + 1]] -= 1
for k in range(1, len(b)):
d[k] += d[k - 1] # cộng dồn
print('\n'.join(str(d[idx[x]]) for x in xs))lower_bound trả về vị trí của một giá trị khác (lớn hơn) và đáp án sai mà không báo lỗi gì. Quy tắc: mọi giá trị mà sau này em sẽ gọi id(...) đều phải được đưa vào b trước khi sắp xếp. Mảng sau khi nén có tới $2n + q$ ô, nhớ khai báo đủ.Phần 5Ứng dụng: điểm được phủ nhiều nhất, xếp phòng ít nhất
1. Điểm được phủ nhiều nhất là điểm nào? Ở phần 3 ta chỉ in số lượng. Muốn biết cả vị trí, chỉ cần nhớ thời điểm của sự kiện làm best tăng: ngay sau một sự kiện $+1$ tại $t$, các điểm từ $t$ tới trước sự kiện tiếp theo đều có đúng cur đoạn phủ. Vì ta cập nhật khi cur > best (lớn hơn hẳn), thời điểm lưu lại là điểm nhỏ nhất đạt kỷ lục. Trong ví dụ Hình 1 đó là điểm 3 (bài tập 5).
for(auto e : ev){
cur += e.second;
if(cur > best){ best = cur; diem = e.first; } // e.first là thời điểm của sự kiện +1
}2. Xếp phòng ít nhất. Khách sạn có $n$ khách, khách $i$ ở từ ngày $a_i$ tới hết ngày $b_i$. Hai khách ở cùng phòng thì khoảng ngày không được giao nhau. Cần ít nhất bao nhiêu phòng, và xếp ai vào phòng nào?
Số phòng ít nhất bằng đúng số khách có mặt cùng lúc nhiều nhất (phần 3): ít hơn thì vào ngày đông nhất sẽ thiếu phòng, còn cách tham lam dưới đây dùng đúng chừng đó phòng. Tham lam theo tinh thần bài 18: xét khách theo ngày đến tăng dần. Với mỗi khách, nhìn phòng sẽ được trả sớm nhất; nếu phòng ấy đã trống trước ngày khách đến thì cho khách vào đó, nếu không thì mọi phòng đều đang có người, phải mở phòng mới.
Để lấy nhanh “phòng trả sớm nhất”, ta dùng hàng đợi ưu tiên priority_queue: một cấu trúc luôn cho biết phần tử nhỏ nhất (hoặc lớn nhất) trong $O(1)$, thêm và xoá trong $O(\log n)$. Mặc định priority_queue của C++ đưa phần tử lớn nhất lên đỉnh; muốn nhỏ nhất thì khai báo thêm greater. Python dùng thư viện heapq, vốn luôn đưa nhỏ nhất lên đầu h[0].
| Khách (theo ngày đến) | [a, b] | Đỉnh hàng đợi (ngày trả, phòng) | Quyết định |
|---|---|---|---|
| 1 | [1, 2] | (trống) | mở phòng 1 |
| 4 | [1, 5] | (2, phòng 1): 2 không < 1 | mở phòng 2 |
| 2 | [2, 4] | (2, phòng 1): 2 không < 2, hôm nay khách 1 vẫn ở | mở phòng 3 |
| 3 | [4, 4] | (2, phòng 1): 2 < 4 | vào phòng 1 |
| 5 | [6, 7] | (4, phòng 1): 4 < 6 | vào phòng 1 |
Bảng 5. Năm khách [1, 2], [2, 4], [4, 4], [1, 5], [6, 7] cần 3 phòng: ngày 2 có khách 1, 2, 4 cùng ở.
Xem code C++ / Python: xếp phòng ít nhất bằng priority_queue (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<array<int, 3>> c(n); // (ngày đến, ngày đi, chỉ số khách)
for(int i = 0; i < n; i++){ cin >> c[i][0] >> c[i][1]; c[i][2] = i; }
sort(c.begin(), c.end()); // ai đến sớm xếp trước
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // (ngày đi, phòng), nhỏ nhất ở đỉnh
vector<int> phong(n);
int k = 0;
for(auto &x : c){
int room;
if(!pq.empty() && pq.top().first < x[0]){ // phòng trả sớm nhất đã trống
room = pq.top().second; pq.pop();
} else room = ++k; // không có phòng trống: mở phòng mới
phong[x[2]] = room;
pq.push({x[1], room});
}
cout << k << "\n";
for(int i = 0; i < n; i++) cout << phong[i] << " ";
return 0;
}import sys, heapq
data = sys.stdin.buffer.read().split()
n = int(data[0])
c = sorted((int(data[1 + 2 * i]), int(data[2 + 2 * i]), i) for i in range(n)) # ai đến sớm xếp trước
pq = [] # (ngày đi, phòng), nhỏ nhất ở đỉnh
phong = [0] * n
k = 0
for a, b, i in c:
if pq and pq[0][0] < a: # phòng trả sớm nhất đã trống
room = heapq.heappop(pq)[1]
else: # không có phòng trống: mở phòng mới
k += 1
room = k
phong[i] = room
heapq.heappush(pq, (b, room))
print(k)
print(*phong)“Tổng chiều dài được phủ”, “gộp các khoảng thời gian” → sắp xếp theo đầu trái, gộp đoạn (hoặc quét sự kiện, cộng độ dài khi
cur > 0).“Giá trị tới $10^9$ nhưng chỉ có $n \le 2 \cdot 10^5$ số”, cần mảng đếm / mảng hiệu → nén số trước.
- Collecting Numbers (CSES 2216) (Dễ)
- Restaurant Customers (CSES 1619) (Trung bình)
- Chiều dài phủ (DOANP2) (Trung bình)
- Dây Đèn (HSG9 Hà Nội 2025 – Bài 3) (Trung bình)
- Room Allocation (CSES 1164) (Khá)
- Điểm chung (Khá)
- Dịch chuyển tức thời (Khó)
Bài tậpLuyện sắp xếp, sự kiện và nén số
Lớp có $n$ bạn ($2 \le n \le 2 \cdot 10^5$), bạn thứ $i$ cao $a_i$ ($1 \le a_i \le 10^9$). Tìm $d$ là chênh lệch chiều cao nhỏ nhất giữa hai bạn khác nhau, và đếm xem có bao nhiêu cặp bạn $(i, j)$, $i < j$, có chênh lệch đúng bằng $d$. In $d$ và số cặp.
6
5 1 9 3 7 112 5📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for(auto &x : a) cin >> x;
sort(a.begin(), a.end());
long long d = LLONG_MAX, cnt = 0;
for(int i = 1; i < n; i++) d = min(d, a[i] - a[i - 1]);
if(d > 0){
for(int i = 1; i < n; i++) if(a[i] - a[i - 1] == d) cnt++;
} else {
for(int i = 0, j; i < n; i = j){ // duyệt từng cụm số bằng nhau
j = i;
while(j < n && a[j] == a[i]) j++;
long long k = j - i;
cnt += k * (k - 1) / 2;
}
}
cout << d << " " << cnt;
return 0;
}import sys
from collections import Counter
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = sorted(map(int, data[1:n + 1]))
d = min(a[i] - a[i - 1] for i in range(1, n))
if d > 0:
cnt = sum(1 for i in range(1, n) if a[i] - a[i - 1] == d)
else:
cnt = sum(k * (k - 1) // 2 for k in Counter(a).values()) # mỗi cụm k số bằng nhau
print(d, cnt)Cho dãy $n$ số nguyên ($n \le 2 \cdot 10^5$, $|a_i| \le 10^{18}$). Hãy thay mỗi số bằng thứ hạng của nó: số nhỏ nhất có hạng 1, các số bằng nhau cùng hạng, và hạng của các giá trị khác nhau liên tiếp nhau (không bỏ trống hạng nào). In dãy thứ hạng.
6
100 -7 100 3000000 0 -73 1 3 4 2 1📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for(auto &x : a) cin >> x;
vector<long long> b = a;
sort(b.begin(), b.end());
b.erase(unique(b.begin(), b.end()), b.end());
for(int i = 0; i < n; i++)
cout << lower_bound(b.begin(), b.end(), a[i]) - b.begin() + 1 << " ";
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
a = list(map(int, data[1:n + 1]))
idx = {v: i + 1 for i, v in enumerate(sorted(set(a)))}
print(*[idx[x] for x in a])Hàng rào là trục số. Có $n$ lần sơn ($n \le 2 \cdot 10^5$), lần thứ $i$ sơn khúc từ toạ độ $l_i$ tới $r_i$ ($-10^9 \le l_i \le r_i \le 10^9$). Tính tổng chiều dài phần hàng rào đã được sơn (khúc được sơn nhiều lần chỉ tính một lần).
5
-3 1
0 2
5 6
6 9
4 510📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
int.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<pair<long long, long long>> a(n);
for(auto &p : a) cin >> p.first >> p.second;
sort(a.begin(), a.end());
long long L = a[0].first, R = a[0].second, tong = 0;
for(int i = 1; i < n; i++){
if(a[i].first <= R) R = max(R, a[i].second);
else { tong += R - L; L = a[i].first; R = a[i].second; }
}
tong += R - L;
cout << tong;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
seg = sorted((int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(n))
L, R = seg[0]
tong = 0
for l, r in seg[1:]:
if l <= R:
R = max(R, r)
else:
tong += R - L
L, R = l, r
print(tong + R - L)Có $n$ nhóm khách ($n \le 2 \cdot 10^5$). Nhóm thứ $i$ gồm $w_i$ người ($1 \le w_i \le 10^9$), đến lúc $a_i$ và rời đi lúc $b_i$ ($0 \le a_i < b_i \le 10^9$). Nhóm rời đi lúc $t$ thì không còn ở đó khi một nhóm khác đến đúng lúc $t$. Hỏi lúc đông nhất nhà hàng có bao nhiêu người?
4
1 5 3
2 4 2
4 8 5
5 6 18📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
(t, w) với $w$ âm cho sự kiện rời đi đã tự đưa sự kiện rời lên trước. Ví dụ: lúc 4, nhóm 2 (2 người) rời rồi nhóm 3 (5 người) đến, nhà hàng có $3 + 5 = 8$ người. Tổng số người có thể tới $2 \cdot 10^{14}$: dùng long long.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<pair<long long, long long>> ev;
for(int i = 0; i < n; i++){
long long a, b, w;
cin >> a >> b >> w;
ev.push_back({a, w});
ev.push_back({b, -w}); // -w < w nên rời đi được xử lý trước
}
sort(ev.begin(), ev.end());
long long cur = 0, best = 0;
for(auto e : ev){
cur += e.second;
best = max(best, cur);
}
cout << best;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
ev = []
for i in range(n):
a, b, w = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])
ev.append((a, w))
ev.append((b, -w)) # -w < w nên rời đi được xử lý trước
ev.sort()
cur = best = 0
for t, d in ev:
cur += d
if cur > best:
best = cur
print(best)Cho $n$ đoạn số nguyên $[l_i, r_i]$ ($n \le 2 \cdot 10^5$, $-10^9 \le l_i \le r_i \le 10^9$), đoạn phủ mọi điểm nguyên từ $l_i$ tới $r_i$. Tìm số đoạn lớn nhất cùng phủ một điểm nguyên, và điểm nhỏ nhất đạt được số đó.
4
1 3
2 5
5 7
4 63 5📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
cur > best (lớn hơn hẳn) thì cập nhật best và lưu thời điểm của sự kiện đó, như phần 5. Ví dụ: điểm 5 được [2, 5], [5, 7], [4, 6] phủ. Tại $t = 4$ có $(4, -1)$ của [1, 3] và $(4, +1)$ của [4, 6], trừ trước nên cur chỉ là 2.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<pair<long long, int>> ev;
for(int i = 0; i < n; i++){
long long l, r;
cin >> l >> r;
ev.push_back({l, +1});
ev.push_back({r + 1, -1});
}
sort(ev.begin(), ev.end());
int cur = 0, best = 0;
long long diem = 0;
for(auto e : ev){
cur += e.second;
if(cur > best){ best = cur; diem = e.first; }
}
cout << best << " " << diem;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n = int(data[0])
ev = []
for i in range(n):
l, r = int(data[1 + 2 * i]), int(data[2 + 2 * i])
ev.append((l, 1))
ev.append((r + 1, -1))
ev.sort()
cur = best = diem = 0
for t, d in ev:
cur += d
if cur > best:
best, diem = cur, t
print(best, diem)Cho $n$ đoạn $[l_i, r_i]$ ($n \le 2 \cdot 10^5$, $0 \le l_i \le r_i \le 10^9$) và $q$ điểm $x_j$ ($q \le 2 \cdot 10^5$, $0 \le x_j \le 10^9$). Với mỗi điểm, in số đoạn chứa điểm đó ($l_i \le x_j \le r_i$).
4 5
1 3
2 5
5 7
4 6
0 2 5 6 1000
2
3
2
0📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
upper_bound(L, x) và lower_bound(R, x). Với $x = 5$: có 4 đoạn có $l \le 5$, 1 đoạn có $r < 5$, đáp án 3.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<long long> L(n), R(n);
for(int i = 0; i < n; i++) cin >> L[i] >> R[i];
sort(L.begin(), L.end());
sort(R.begin(), R.end());
while(q--){
long long x;
cin >> x;
long long batDau = upper_bound(L.begin(), L.end(), x) - L.begin(); // số đoạn có l <= x
long long daHet = lower_bound(R.begin(), R.end(), x) - R.begin(); // số đoạn có r < x
cout << batDau - daHet << "\n";
}
return 0;
}import sys
from bisect import bisect_left, bisect_right
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
L = sorted(int(data[2 + 2 * i]) for i in range(n))
R = sorted(int(data[3 + 2 * i]) for i in range(n))
out = []
for j in range(q):
x = int(data[2 + 2 * n + j])
out.append(bisect_right(L, x) - bisect_left(R, x)) # (l <= x) - (r < x)
print('\n'.join(map(str, out)))Có $n$ khách ($n \le 2 \cdot 10^5$), khách $i$ ở từ ngày $a_i$ tới hết ngày $b_i$ ($1 \le a_i \le b_i \le 10^9$). Khách sạn phân phòng như sau: xét khách theo ngày đến tăng dần (cùng ngày đến thì khách có số thứ tự nhỏ hơn trước). Phòng được coi là trống với khách đến ngày $a$ nếu người ở trước đã đi từ ngày $b < a$. Nếu có phòng trống, khách nhận phòng trống có số nhỏ nhất; nếu không, khách sạn mở phòng mới với số tiếp theo (1, 2, 3, …). In số phòng đã mở, rồi số phòng của từng khách theo thứ tự đề cho.
6
1 3
2 5
4 6
1 1
7 8
6 92
1 2 1 2 1 2📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
ban chứa các cặp (ngày trả, phòng) đang có người, trong chứa số các phòng trống. Khi khách đến ngày $a$: lấy hết các phòng ở đỉnh ban có ngày trả $< a$ chuyển sang trong; nếu trong khác rỗng thì lấy phòng số nhỏ nhất, ngược lại mở phòng mới. Mỗi phòng vào ra mỗi hàng đợi tối đa $n$ lần nên tổng $O(n \log n)$. Ví dụ: khách 4 ở ngày 1 nên khách 2 (đến ngày 2) nhận lại phòng 2; số phòng mở ra bằng số khách cùng lúc nhiều nhất là 2.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n;
cin >> n;
vector<array<int, 3>> c(n); // (ngày đến, số thứ tự, ngày đi)
for(int i = 0; i < n; i++){ cin >> c[i][0] >> c[i][2]; c[i][1] = i; }
sort(c.begin(), c.end()); // cùng ngày đến: số thứ tự nhỏ trước
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> ban; // (ngày trả, phòng)
priority_queue<int, vector<int>, greater<int>> trong; // phòng trống
vector<int> phong(n);
int k = 0;
for(auto &x : c){
while(!ban.empty() && ban.top().first < x[0]){ trong.push(ban.top().second); ban.pop(); }
int room;
if(!trong.empty()){ room = trong.top(); trong.pop(); }
else room = ++k;
phong[x[1]] = room;
ban.push({x[2], room});
}
cout << k << "\n";
for(int i = 0; i < n; i++) cout << phong[i] << " ";
return 0;
}import sys, heapq
data = sys.stdin.buffer.read().split()
n = int(data[0])
c = sorted((int(data[1 + 2 * i]), i, int(data[2 + 2 * i])) for i in range(n)) # cùng ngày đến: số thứ tự nhỏ trước
ban, trong = [], [] # ban: (ngày trả, phòng); trong: số phòng trống
phong = [0] * n
k = 0
for a, i, b in c:
while ban and ban[0][0] < a:
heapq.heappush(trong, heapq.heappop(ban)[1])
if trong:
room = heapq.heappop(trong)
else:
k += 1
room = k
phong[i] = room
heapq.heappush(ban, (b, room))
print(k)
print(*phong)Có $n$ tấm bạt ($n \le 2 \cdot 10^5$) trải trên trục số, tấm thứ $i$ che khúc $[l_i, r_i)$ ($0 \le l_i < r_i \le 10^9$). Cho số $k$ ($1 \le k \le n$). Tính tổng chiều dài phần trục số được ít nhất $k$ tấm bạt che.
5 2
0 4
2 6
3 8
10 12
11 155📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
cur. Nếu cur $\ge k$ thì cộng $t_{i+1} - t_i$. Sự kiện trùng thời điểm cho khúc dài 0 nên thứ tự không ảnh hưởng. Ví dụ: khúc [2, 6) được 2–3 tấm che (dài 4), khúc [11, 12) được 2 tấm che (dài 1), tổng 5. Gộp đoạn ở phần 2 chính là trường hợp $k = 1$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<pair<long long, int>> ev;
for(int i = 0; i < n; i++){
long long l, r;
cin >> l >> r;
ev.push_back({l, +1});
ev.push_back({r, -1});
}
sort(ev.begin(), ev.end());
int cur = 0;
long long ans = 0;
for(int i = 0; i + 1 < (int)ev.size(); i++){
cur += ev[i].second;
if(cur >= k) ans += ev[i + 1].first - ev[i].first; // khúc [t_i, t_{i+1}) có cur tấm che
}
cout << ans;
return 0;
}import sys
data = sys.stdin.buffer.read().split()
n, k = int(data[0]), int(data[1])
ev = []
for i in range(n):
l, r = int(data[2 + 2 * i]), int(data[3 + 2 * i])
ev.append((l, 1))
ev.append((r, -1))
ev.sort()
cur = ans = 0
for i in range(len(ev) - 1):
cur += ev[i][1]
if cur >= k:
ans += ev[i + 1][0] - ev[i][0] # khúc [t_i, t_{i+1}) có cur tấm che
print(ans)
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét