Sort, pair và comparator
- Độ khó
- ★★★☆☆ Vừa
- Thời lượng
- Khoảng 90 phút
- Học trước
- Sắp xếp cơ bản
- Chủ đề
- comparatorpairsắp xếp
- Trạng thái
Kiến thức cơ bản
Vì sao cần hàm sort có sẵn
Ở tuần 10, em đã tự viết sắp xếp chọn và sắp xếp nổi bọt. Hai cách này giống như Gấu Po tự tay xếp từng cuốn sách vào tủ: rất dễ hiểu nhưng mất khoảng n2 phép tính. Với n = 105 thì n2 = 1010, chậm hơn quy ước 108 rất nhiều.
C++ có sẵn hàm sort, giống một "người thủ thư siêu tốc": chỉ mất khoảng n × log n phép tính. Với n = 105 thì chỉ cỡ 1,7 × 106 phép tính, máy tính chạy trong một cái chớp mắt. Em đã hiểu cách sắp xếp hoạt động bên trong từ tuần 10, nên khi làm bài thi em có thể yên tâm dùng sort.
Nhưng đôi khi ta cần xếp theo luật riêng: điểm cao đứng trước, tên ngắn đứng trước, số gần X đứng trước,... Để làm được, em cần học thêm hai công cụ: pair (gói hai thông tin làm một) và hàm so sánh (luật xếp hàng do em tự đặt).
Hàm sort
Để dùng sort, ta cần thư viện: #include <algorithm>. Cú pháp: sort(đầu, cuối); hàm sắp xếp các phần tử từ vị trí "đầu" đến ngay trước vị trí "cuối" (lấy đầu, không lấy cuối). Mặc định là sắp xếp tăng dần.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int a[5] = {5, 2, 9, 1, 7};
sort(a, a + 5); // mảng, tăng dần: 1 2 5 7 9
vector<int> v = {5, 2, 9, 1, 7};
sort(v.begin(), v.end()); // vector, tăng dần
sort(v.begin(), v.end(), greater<int>()); // giảm dần
string s = "banana";
sort(s.begin(), s.end()); // xâu: aaabnn
for (int x : v) cout << x << " ";
return 0;
}
Các tính chất của sort
- Độ phức tạp của sort là O(n log n), nhanh hơn rất nhiều so với O(n2) của sắp xếp chọn và nổi bọt.
- Mảng đánh số từ 0 có n phần tử: sort(a, a + n). Mảng đánh số từ 1: sort(a + 1, a + n + 1). Lỗi hay gặp: viết sort(a, a + n - 1) làm bỏ sót phần tử cuối.
- Sort một đoạn: sort(a + 2, a + 6) chỉ sắp xếp a[2], a[3], a[4], a[5], các phần tử còn lại đứng yên.
- Xâu ký tự được xếp theo mã ký tự; vector<string> được xếp theo thứ tự từ điển.
- Sort không đảm bảo giữ nguyên thứ tự ban đầu của các phần tử bằng nhau. Nếu cần giữ thứ tự, dùng stable_sort (không bắt buộc).
Cặp pair
Thỏ ghi sổ điểm lớp: mỗi bạn có hai thông tin là điểm và tên. Nếu để hai thông tin này ở hai vector riêng thì khi sắp xếp, điểm và tên rất dễ bị lệch nhau. C++ có sẵn pair, một chiếc hộp hai ngăn: ngăn thứ nhất tên first, ngăn thứ hai tên second. Sắp xếp các hộp thì cả hai ngăn luôn đi cùng nhau.
pair<int, string> p
+-----------+-----------+
| first | second |
| 9 | "Lan" |
+-----------+-----------+
Khai báo và sử dụng pair
pair<kiểu_1, kiểu_2> tên_biến; (ví dụ: pair<int, string> p;). Dùng thư viện <utility>, thư viện này đã có sẵn khi em #include <algorithm> hoặc <vector>.
pair<int, string> p = {9, "Lan"}; // first = 9, second = "Lan"
p.first = 10; // sửa ngăn thứ nhất
cout << p.first << " " << p.second; // in ra: 10 Lan
pair<int, int> q = make_pair(3, 4); // cách khác để tạo pair
vector<pair<int, string>> ds; // danh sách nhiều "hộp"
ds.push_back({8, "Hoa"}); // thêm một cặp vào cuối
ds.push_back({9, "Lan"});
ds.push_back({8, "An"});
sort(ds.begin(), ds.end()); // sắp xếp mặc định
// Kết quả: {8,An} {8,Hoa} {9,Lan}
for (auto &p : ds) cout << p.first << " " << p.second << "\n";
// Nhập một pair: cin >> p.first >> p.second;
Các tính chất của pair
- Pair được so sánh giống như tra từ điển: so sánh first trước; chỉ khi first bằng nhau mới so sánh tiếp second. Vì vậy sort mặc định một vector<pair> xếp tăng dần theo first, hòa thì tăng dần theo second.
- Hai pair có thể so sánh bằng ==, !=, <, >. Pair cũng gán được cho nhau: p = q;
- Muốn nhớ vị trí ban đầu của một số, ta gói thành pair {giá trị, vị trí}. Sắp xếp xong vẫn biết số đó lúc đầu đứng ở đâu.
- Muốn lưu ba thông tin có thể lồng pair<int, pair<int, int>>: p.first, p.second.first, p.second.second (không bắt buộc).
Hàm so sánh (comparator)
Sắp xếp tăng dần chưa đủ cho mọi trò chơi. Ví dụ Hổ muốn điểm cao đứng trước, hoặc muốn tên ngắn đứng trước. Khi đó em viết một hàm so sánh, giống như luật xếp hàng của lớp. Hàm nhận hai phần tử a và b, và trả về true nếu a phải đứng trước b.
cmp(a, b) trả về true -> a đứng TRƯỚC b
cmp(a, b) trả về false -> a chưa cần đứng trước b
Ví dụ: bool cmp(int a, int b) { return a > b; }
a = 9, b = 4: 9 > 4 đúng -> 9 đứng trước 4
a = 3, b = 7: 3 > 7 sai -> 3 chưa cần đứng trước 7
Kết quả sau khi sort: 9 7 4 3 ... (giảm dần)
// Luật 1: số lớn đứng trước (giảm dần)
bool cmpGiam(int a, int b) {
return a > b;
}
// Luật 2: điểm cao trước; cùng điểm thì tên theo từ điển
bool cmpDiem(const pair<int, string>& a,
const pair<int, string>& b) {
// khác điểm: điểm cao đứng trước
if (a.first != b.first) return a.first > b.first;
// cùng điểm: tên nhỏ hơn đứng trước
return a.second < b.second;
}
int main() {
vector<int> v = {5, 2, 9, 1, 7};
sort(v.begin(), v.end(), cmpGiam); // tên hàm là tham số thứ ba
vector<pair<int, string>> ds;
ds = {{8, "Hoa"}, {9, "Lan"}, {8, "An"}};
sort(ds.begin(), ds.end(), cmpDiem); // {9,Lan} {8,An} {8,Hoa}
return 0;
}
Các tính chất của hàm so sánh
- Hàm so sánh có kiểu trả về là bool và có đúng hai tham số cùng kiểu với phần tử cần sắp xếp. Viết const kiểu& (ví dụ const string& a) để máy không phải sao chép dữ liệu, nhờ đó chạy nhanh hơn.
- Chỉ dùng < hoặc >, không dùng <= hay >=. Nếu hai phần tử bằng nhau mà hàm vẫn trả về true thì sort bị "rối" và chương trình có thể bị lỗi khi chạy (runtime error).
- Nhiều tiêu chí: xét tiêu chí quan trọng nhất trước. Nếu hai phần tử khác nhau ở tiêu chí này thì quyết định luôn; nếu bằng nhau thì xét tiêu chí tiếp theo.
- Mẹo đổi dấu: muốn xếp giảm dần theo số thứ nhất, tăng dần theo số thứ hai, ta có thể lưu {-số_thứ_nhất, số_thứ_hai} rồi dùng sort mặc định. Khi in nhớ đổi dấu lại.
- Hàm so sánh có thể dùng biến toàn cục (khai báo ngoài main). Ví dụ biến X trong bài "Gần X nhất đứng trước".
Một số hàm và cách dùng
| sort(a, a + n) | Sắp xếp mảng a[0..n-1] tăng dần |
|---|---|
| sort(a + 1, a + n + 1) | Sắp xếp mảng đánh số từ 1, tức là a[1..n] |
| sort(v.begin(), v.end()) | Sắp xếp vector hoặc string tăng dần |
| sort(v.begin(), v.end(), greater<int>()) | Sắp xếp giảm dần |
| sort(v.begin(), v.end(), cmp) | Sắp xếp theo luật do em tự viết trong hàm cmp |
| reverse(v.begin(), v.end()) | Đảo ngược thứ tự các phần tử |
| pair<A, B> p; make_pair(x, y); {x, y} | Khai báo pair và các cách tạo pair |
| p.first, p.second | Lấy ngăn thứ nhất, ngăn thứ hai của pair p |
| stable_sort(...) | Như sort nhưng giữ nguyên thứ tự ban đầu của các phần tử bằng nhau (không bắt buộc) |
Khi nào dùng cách nào
| Tình huống | Cách làm | Ví dụ |
|---|---|---|
| Xếp số hoặc xâu tăng dần | sort mặc định | Xếp điểm từ thấp đến cao; xếp tên theo từ điển |
| Xếp giảm dần | greater<int>() hoặc đổi dấu | Xếp tạ từ nặng đến nhẹ |
| Hai thông tin đi cùng nhau | vector<pair>, sort mặc định (first rồi đến second) | Danh sách (tuổi, tên) |
| Thứ tự đặc biệt | Viết hàm cmp | Điểm giảm - tên tăng; số gần X; chẵn trước lẻ sau |
| Cần biết vị trí ban đầu | pair {giá trị, vị trí} | In vị trí ban đầu của các thẻ sau khi xếp |
Luyện tập
Bài 1. Bảng điểm tăng dần
Cô giáo chấm xong bài kiểm tra của n bạn và nhờ Thỏ ghi lên bảng điểm từ thấp đến cao. Em hãy giúp Thỏ nhé.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (0 ≤ a[i] ≤ 109) là điểm của các bạn. | |
|---|---|---|
| Đầu ra | Các điểm sắp xếp tăng dần, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 7 3 9 3 1 | 1 3 3 7 9 |
| 2 | 3 100 50 75 | 50 75 100 |
Bài 2. Gấu Po xếp tạ
Phòng tập của Gấu Po có n quả tạ, mỗi quả có một khối lượng. Gấu Po muốn xếp lên giá theo thứ tự từ nặng nhất đến nhẹ nhất. Hãy in thứ tự khối lượng các quả tạ trên giá.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Các khối lượng theo thứ tự giảm dần, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 6 12 5 30 18 5 7 | 30 18 12 7 5 5 |
| 2 | 1 42 | 42 |
Bài 3. Sổ địa chỉ của Hổ
Hổ có n người bạn trong sổ địa chỉ. Hổ muốn các tên được xếp theo thứ tự từ điển để dễ tìm. Tên chỉ gồm chữ cái thường, không có dấu cách.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n tên, mỗi tên dài không quá 20 ký tự. | |
|---|---|---|
| Đầu ra | Các tên theo thứ tự từ điển, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 mai lan an binh hoa | an binh hoa lan mai |
| 2 | 3 bo bob b | b bo bob |
Bài 4. Bạn đứng giữa
Lớp có n bạn (n là số lẻ) xếp hàng dọc theo chiều cao từ thấp đến cao. Thỏ muốn biết bạn đứng chính giữa hàng cao bao nhiêu (gọi là chiều cao trung vị).
| Đầu vào | Dòng 1: số nguyên lẻ n (1 ≤ n ≤ 99999). Dòng 2: n số nguyên a[i] (100 ≤ a[i] ≤ 200) là chiều cao các bạn, tính bằng cm. | |
|---|---|---|
| Đầu ra | Chiều cao của bạn đứng chính giữa hàng. | |
| Test | Input | Output |
| 1 | 5 150 142 160 138 155 | 150 |
| 2 | 1 120 | 120 |
Bài 5. Danh sách theo tuổi
Câu lạc bộ có n bạn, mỗi bạn có tuổi và tên. Hổ muốn lập danh sách theo tuổi tăng dần; các bạn cùng tuổi thì xếp theo thứ tự từ điển của tên. Gợi ý: gói mỗi bạn vào một pair.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng tiếp theo: mỗi dòng gồm số nguyên tuổi (6 ≤ tuổi ≤ 100) và tên (chữ thường, không quá 20 ký tự). | |
|---|---|---|
| Đầu ra | n dòng, mỗi dòng gồm tuổi và tên, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 4 12 lan 11 mai 12 an 11 hoa | 11 hoa 11 mai 12 an 12 lan |
| 2 | 3 12 tho 12 ho 12 po | 12 ho 12 po 12 tho |
Bài 6. Bảng xếp hạng cuộc thi
Thỏ tổ chức cuộc thi giải đố cho n bạn. Bảng xếp hạng cần điểm cao đứng trên; hai bạn cùng điểm thì bạn có tên đứng trước theo thứ tự từ điển được xếp trên. Hãy viết hàm so sánh để in bảng xếp hạng.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng tiếp theo: mỗi dòng gồm tên (chữ thường, không quá 20 ký tự, không trùng nhau) và điểm (0 ≤ điểm ≤ 1000). | |
|---|---|---|
| Đầu ra | n dòng, mỗi dòng gồm tên và điểm theo thứ tự xếp hạng. | |
| Test | Input | Output |
| 1 | 5 lan 8 an 9 mai 8 hoa 10 binh 9 | hoa 10 an 9 binh 9 lan 8 mai 8 |
| 2 | 2 po 5 tho 7 | tho 7 po 5 |
Bài 7. Mua sách rẻ nhất
Thỏ có một cửa hàng sách gồm n cuốn, cuốn thứ i có giá a[i] đồng. Thỏ muốn mua đúng k cuốn rẻ nhất để làm quà. Hỏi Thỏ phải trả tất cả bao nhiêu tiền? Chú ý: tổng tiền có thể rất lớn, hãy dùng long long.
| Đầu vào | Dòng 1: hai số nguyên n, k (1 ≤ k ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng giá tiền của k cuốn sách rẻ nhất. | |
| Test | Input | Output |
| 1 | 6 3 50 20 80 10 40 30 | 60 |
| 2 | 3 3 1000000000 1000000000 1000000000 | 3000000000 |
Bài 8. Hai chú ong gần nhau nhất
Trên một thanh gỗ dài có n chú ong đậu, chú thứ i đậu ở vị trí a[i]. Hổ muốn biết hai chú ong nào đậu gần nhau nhất và khoảng cách giữa chúng là bao nhiêu. Chú ý: nếu so sánh mọi cặp thì mất khoảng n2 phép tính, quá chậm. Hãy nghĩ xem sau khi sắp xếp, hai chú gần nhau nhất sẽ nằm ở đâu.
| Đầu vào | Dòng 1: số nguyên n (2 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). Có thể có hai chú đậu cùng vị trí. | |
|---|---|---|
| Đầu ra | Khoảng cách nhỏ nhất giữa hai chú ong. | |
| Test | Input | Output |
| 1 | 5 10 4 25 7 18 | 3 |
| 2 | 3 5 5 9 | 0 |
Bài 9. Vị trí ban đầu của các thẻ
Gấu Po có n tấm thẻ đánh số vị trí từ 1 đến n, thẻ thứ i ghi số a[i]. Gấu Po muốn xếp các thẻ theo số ghi trên thẻ từ nhỏ đến lớn, nhưng vẫn cần nhớ vị trí ban đầu của mỗi thẻ. Hãy in ra vị trí ban đầu của các thẻ theo thứ tự đã xếp. Nếu hai thẻ ghi số bằng nhau thì thẻ có vị trí nhỏ hơn đứng trước.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | n số nguyên là vị trí ban đầu của các thẻ sau khi xếp, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 30 10 20 10 40 | 2 4 3 1 5 |
| 2 | 3 5 5 5 | 1 2 3 |
Bài tập tự luyện
Bài 1. Số lớn nhất từ các chữ số
Hổ có một số rất dài và muốn xáo trộn các chữ số của nó để được số lớn nhất có thể. Gợi ý: số được cho dưới dạng xâu ký tự.
| Đầu vào | Một dòng duy nhất là xâu s gồm các chữ số (1 ≤ độ dài s ≤ 105). | |
|---|---|---|
| Đầu ra | Xâu gồm các chữ số của s sắp xếp lại để được giá trị lớn nhất. | |
| Test | Input | Output |
| 1 | 40517 | 75410 |
| 2 | 2020 | 2200 |
Bài 2. Bỏ trùng bằng sort
Gấu Po nhận được n tấm vé số, nhiều vé ghi trùng số. Gấu Po muốn biết có bao nhiêu số khác nhau và liệt kê chúng theo thứ tự tăng dần. Gợi ý: sau khi sắp xếp, các số bằng nhau nằm cạnh nhau.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Dòng 1: số lượng giá trị khác nhau. Dòng 2: các giá trị khác nhau theo thứ tự tăng dần, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 7 4 2 4 9 2 7 9 | 4 2 4 7 9 |
| 2 | 3 5 5 5 | 1 5 |
Bài 3. Ghép cặp cân bằng
Có 2n bạn tham gia trò chơi đôi, bạn thứ i có sức mạnh a[i]. Thỏ chia 2n bạn thành đúng n cặp, sức mạnh của một cặp là tổng sức mạnh hai bạn. Thỏ muốn cặp mạnh nhất cũng không quá mạnh, nghĩa là giá trị sức mạnh lớn nhất trong các cặp phải nhỏ nhất có thể. Hãy tính giá trị nhỏ nhất đó. Gợi ý: nên ghép bạn mạnh nhất với bạn yếu nhất.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 5×104). Dòng 2: 2n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Giá trị nhỏ nhất có thể của sức mạnh cặp mạnh nhất. | |
| Test | Input | Output |
| 1 | 2 1 2 3 4 | 5 |
| 2 | 3 5 5 1 1 9 2 | 10 |
Bài 4. Gần X nhất đứng trước
Hổ có n số và một số X cho trước. Hổ muốn xếp các số theo khoảng cách đến X từ gần đến xa. Hai số có cùng khoảng cách thì số nhỏ hơn đứng trước. Gợi ý: hàm so sánh có thể dùng biến X khai báo ở ngoài hàm main.
| Đầu vào | Dòng 1: hai số nguyên n, X (1 ≤ n ≤ 105, 1 ≤ X ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Các số sau khi sắp xếp, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 10 3 12 10 8 20 | 10 8 12 3 20 |
| 2 | 3 5 1 9 5 | 5 1 9 |
Bài 5. Chẵn trước lẻ sau
Thỏ muốn xếp n tấm thẻ như sau: các thẻ mang số chẵn đứng trước và xếp tăng dần, sau đó đến các thẻ mang số lẻ và xếp giảm dần. Em hãy viết hàm so sánh giúp Thỏ.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Các số sau khi sắp xếp, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 8 5 2 8 1 4 9 7 6 | 2 4 6 8 9 7 5 1 |
| 2 | 3 3 1 2 | 2 3 1 |
Bài 6. Từ ngắn đứng trước
Gấu Po viết n từ lên bảng và muốn sắp xếp chúng: từ ngắn đứng trước từ dài; hai từ cùng độ dài thì theo thứ tự từ điển. Từ chỉ gồm chữ cái thường, không có dấu cách.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n từ, mỗi từ dài không quá 20 ký tự. | |
|---|---|---|
| Đầu ra | Các từ sau khi sắp xếp, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 6 gau tho ho po cop ga | ga ho po cop gau tho |
| 2 | 3 abc ab a | a ab abc |
Bài 7. Thứ hạng của từng bạn
Trong cuộc thi chạy, n bạn có điểm a[i]. Thứ hạng của một bạn bằng 1 cộng với số bạn có điểm cao hơn bạn đó (các bạn cùng điểm có cùng thứ hạng). Hãy in thứ hạng của từng bạn theo thứ tự nhập. Gợi ý: dùng pair để nhớ vị trí ban đầu.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (0 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | n số nguyên, số thứ i là thứ hạng của bạn thứ i, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 80 95 80 70 95 | 3 1 3 5 1 |
| 2 | 3 7 7 7 | 1 1 1 |
Bài 8. Món quà phổ biến nhất
Gấu Po thống kê n món quà, mỗi món có một mã số. Gấu Po muốn liệt kê các mã số theo độ phổ biến, tức số lần xuất hiện giảm dần. Hai mã có số lần xuất hiện bằng nhau thì mã nhỏ hơn đứng trước. Gợi ý: sắp xếp trước để các mã giống nhau đứng cạnh nhau và dễ đếm, rồi sắp xếp một lần nữa.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 109). | |
|---|---|---|
| Đầu ra | Mỗi mã khác nhau một dòng gồm mã số và số lần xuất hiện, theo thứ tự yêu cầu. | |
| Test | Input | Output |
| 1 | 8 3 1 3 2 1 3 2 5 | 3 3 1 2 2 2 5 1 |
| 2 | 3 9 8 7 | 7 1 8 1 9 1 |
Bài 9. Thử thách: Hợp các đoạn hàng rào
Hổ sơn hàng rào dọc một con đường thẳng. Lần thứ i, Hổ sơn đoạn từ vị trí l[i] đến vị trí r[i]. Các đoạn có thể chồng lên nhau, phần bị sơn nhiều lần vẫn chỉ tính một lần. Hỏi tổng độ dài đoạn đường đã được sơn là bao nhiêu? Gợi ý: sắp xếp các đoạn theo điểm đầu rồi đi từ trái sang phải, luôn nhớ đoạn đang gộp hiện tại.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 105). n dòng tiếp theo: mỗi dòng gồm hai số nguyên l, r (1 ≤ l < r ≤ 109). | |
|---|---|---|
| Đầu ra | Tổng độ dài phần đường được sơn. | |
| Test | Input | Output |
| 1 | 3 1 5 3 8 10 12 | 9 |
| 2 | 2 1 10 2 4 | 9 |
- Gợi ý chung: Khi viết hàm so sánh, hãy tự hỏi "nếu hai phần tử bằng nhau thì hàm trả về gì?". Câu trả lời phải là false, nên chỉ dùng < hoặc >, tuyệt đối không dùng <= hay >=. Khi cộng nhiều số lớn (như tổng tiền, tổng độ dài), hãy dùng long long để không bị tràn số. Và khi cần biết vị trí ban đầu hay đếm số lần xuất hiện, hãy nghĩ đến việc gói thông tin vào pair rồi mới sort.