Sorting in C++

ISắp rồi quét cặp kề

Bài toán: cho dãy $x_1, \dots, x_n$, tìm $\min |x_i - x_j|$ với $i \ne j$. Gọi $a$ là dãy sau khi sắp tăng dần. Hiệu nhỏ nhất luôn đạt ở một cặp kề $(a_{i-1}, a_i)$, vì với $i < j$ bất kỳ,

là tổng các hiệu kề không âm, nên $a_j - a_i \ge a_{i+1} - a_i$. Với $x = (17, 4, 9, 25, 12, 31)$, dãy đã sắp là $(4, 9, 12, 17, 25, 31)$, các hiệu kề là $5, 3, 5, 8, 6$, và đáp án $3$ ứng với cặp $(9, 12)$.

sort(a + 1, a + n + 1);
ll ans = 1e18;
for (ll i = 2; i <= n; i++) ans = min(ans, a[i] - a[i - 1]);

sort tốn $O(n \log n)$, với $\log n$ là $\log_2 n$, số lần chia đôi $n$ cho tới khi còn 1 (bài 11 khóa C++). Với $n = 2 \cdot 10^5$ con số này chỉ khoảng 18, nên sắp xếp tốn cỡ $3{,}5 \cdot 10^6$ phép so sánh, nhanh hơn thử mọi cặp hàng nghìn lần.

Dãy đã sắp còn cho thêm vài thứ gần như miễn phí. Các giá trị bằng nhau thành một khối liền, nên số giá trị phân biệt là số vị trí có $a_i \ne a_{i-1}$ cộng một. Phần tử nhỏ thứ $k$ là $a_k$, một trung vị là phần tử đứng giữa, a[(n + 1) / 2]. Chỉ cần một lần giá trị nhỏ nhất hay lớn nhất thì không cần sắp, duyệt một lượt là đủ. Sắp xếp đáng giá khi bài cần nhiều thông tin thứ tự cùng lúc, và thường đi kèm hai con trỏ (bài 0.7) hoặc chặt nhị phân (bài 0.6).

Ví dụBộ Xếp Hình Đồng Đều

Đề. Có $m \le 50$ bộ xếp hình, bộ $i$ có $f_i$ mảnh. Chọn đúng $n$ bộ khác nhau để số mảnh lớn nhất trừ nhỏ nhất là nhỏ nhất.

Lời giải. Sắp $f$ tăng dần. Một cách chọn tốt nhất luôn là $n$ bộ liên tiếp trong dãy đã sắp: nếu cách chọn có min là $f_l$ và max là $f_r$, thay nó bằng $n$ bộ $f_l, \dots, f_{l+n-1}$ không làm max tăng, vì $f_{l+n-1} \le f_r$. Vậy chỉ cần thử mọi cửa sổ $[l, l + n - 1]$ và lấy $f_{l+n-1} - f_l$ nhỏ nhất.

Độ phức tạp: cả bài $O(m \log m)$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m, f[55];

signed main() {
    cin >> n >> m;
    for (ll i = 1; i <= m; i++) cin >> f[i];
    sort(f + 1, f + m + 1);
    ll ans = 1e18;
    for (ll l = 1; l + n - 1 <= m; l++) ans = min(ans, f[l + n - 1] - f[l]);
    cout << ans << '\n';
}

ChạyInput5 9
14 4 8 9 10 15 6 7 20

Output4

IIHàm so sánh

Trong thi đấu ta không tự viết lại sắp xếp thông thường: std::sort đúng và nhanh, chuẩn C++ bảo đảm $O(n \log n)$ phép so sánh kể cả trường hợp xấu nhất.

sort(a + 1, a + n + 1);
sort(a + 1, a + n + 1, greater<ll>());

pair, tuple, string có sẵn thứ tự từ điển: so thành phần đầu, bằng nhau thì so tiếp. Với thứ tự khác, ta đưa thêm hàm cmp(x, y), trả về true khi $x$ phải đứng trước $y$ một cách chặt chẽ. Hàm này phải là thứ tự yếu chặt (strict weak ordering):

• cmp(x, x) luôn sai;
• nếu cmp(x, y) đúng thì cmp(y, x) sai;
• nếu cmp(x, y) và cmp(y, z) đúng thì cmp(x, z) đúng;
• quan hệ “ngang hàng” (cả hai chiều đều sai) có tính bắc cầu.

Cách dễ nhất để thỏa cả bốn là gán mỗi phần tử một khóa và chỉ so khóa bằng < hoặc > chặt. Lỗi hay gặp nhất là viết <= hay >= với ý “bằng nhau cũng được”: một phần tử bị coi là đứng trước chính nó có thể khiến vòng quét bên trong sort chạy ra ngoài mảng, nên chương trình đúng ở test nhỏ rồi sập khi dữ liệu có nhiều giá trị bằng nhau.

std::sort không ổn định (stable): thứ tự các phần tử bằng nhau là không xác định. Khi đề cần thứ tự duy nhất, thêm một khóa phân định (chỉ số gốc, tên); khi muốn giữ thứ tự nhập, dùng stable_sort. Khuôn của hàm nhiều khóa: khóa này khác nhau thì trả lời ngay theo nó, bằng thì sang khóa sau, khóa cuối là một phép so sánh chặt. Khi cần in số hiệu thay vì giá trị, ta sắp một mảng chỉ số, hoặc gói chỉ số vào bản ghi như ví dụ dưới.

Ví dụSắp Xếp Hồ Sơ Địa Điểm

Đề. $N \le 100$ hồ sơ, hồ sơ $i$ có tên thành phố $S_i$ và điểm $P_i$ (đôi một khác nhau). Sắp theo tên tăng dần; cùng thành phố thì điểm cao đứng trước. In chỉ số ban đầu theo thứ tự mới.

Lời giải. Mỗi hồ sơ là một bản ghi (tên, điểm, chỉ số). Hai khóa ngược chiều nhau nên viết hàm so sánh: tên khác nhau thì so tên tăng dần, cùng tên thì so điểm giảm dần. Điểm đôi một khác nhau nên không còn hòa, không cần khóa thứ ba.

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

struct Rec {
    string city;
    ll score, id;
};

bool cmp(Rec x, Rec y) {
    if (x.city != y.city) return x.city < y.city;
    return x.score > y.score;
}

ll n;
Rec a[105];

signed main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> a[i].city >> a[i].score;
        a[i].id = i;
    }
    sort(a + 1, a + n + 1, cmp);
    for (ll i = 1; i <= n; i++) cout << a[i].id << '\n';
}

ChạyInput5
delta 70
alpha 30
alpha 90
delta 50
beta 60

Output3
2
5
1
4

IIITự chọn thứ tự

Đề hiếm khi nói “hãy sắp”; ta phải tự chọn thứ tự, bằng hai cách.

Quy về khóa. Gán mỗi phần tử một giá trị dễ sắp sao cho sắp theo khóa đúng là thứ tự cần. Muốn sắp tên theo một bảng chữ cái khác, thay mỗi chữ bằng hạng của nó trong bảng mới. Muốn nhóm các chuỗi là hoán vị chữ cái của nhau, sắp chữ cái trong mỗi chuỗi: chúng cho ra cùng một chuỗi chuẩn.

So sánh cặp. Viết thẳng quy tắc “$x$ đứng trước $y$ khi …”. Ví dụ ưu tiên tỉ lệ $p / t$ lớn: x.p * y.t > y.p * x.t. Nhân chéo thay cho phép chia nên không có số thực, vì so bằng double có thể coi hai tỉ lệ bằng nhau là khác nhau chút ít và phá tính bắc cầu. Nhớ ước lượng tích lớn nhất: $p, t \le 10^9$ cho tích tới $10^{18}$, còn vừa long long.

Để chắc quy tắc so sánh cặp hợp lệ, hãy tìm hàm khóa $f$ sao cho cmp(x, y) đúng khi và chỉ khi $f(x) < f(y)$ (hoặc $>$). $f$ có thể là số thực ta không bao giờ tính ra; có nó thì bốn điều kiện tự đúng.

Còn làm sao biết thứ tự nào là đúng? Phương pháp quen thuộc là đổi chỗ hai phần tử kề nhau: lấy một phương án bất kỳ, xét hai phần tử đứng cạnh nhau và hỏi đổi chỗ thì tốt lên hay tệ đi. Ví dụ: $n$ việc, việc $i$ cần $t_i$ phút, làm lần lượt; chọn thứ tự để tổng thời điểm hoàn thành nhỏ nhất. Nếu hai việc kề nhau $x$ rồi $y$ có $t_x > t_y$ và cùng bắt đầu lúc $S$, tổng thời điểm xong của chúng là $2S + 2t_x + t_y$; đổi chỗ thì là $2S + 2t_y + t_x$, nhỏ hơn đúng $t_x - t_y$, các việc khác không đổi. Vậy phương án tối ưu không có cặp kề nào nghịch thế: $t$ tăng dần. Khuôn lập luận này quay lại ở bài 0.5.

Ví dụGhép Thành Số Lớn Nhất

Đề. $N \le 10^4$ thẻ, mỗi thẻ ghi số nguyên dương $a_i \le 99$. Xếp thành một hàng rồi đọc liền các số để được số lớn nhất, in số đó.

Lời giải. Mọi cách xếp cho chuỗi cùng độ dài, nên so hai kết quả là so hai chuỗi. Ký hiệu $\overline{xy}$ là số thu được khi viết $x$ rồi $y$. Với hai thẻ kề nhau, phần đứng trước và sau chúng không đổi khi hoán đổi, nên đổi chỗ có lợi khi và chỉ khi $\overline{yx} > \overline{xy}$. Sắp theo quy tắc “$x$ đứng trước $y$ khi $\overline{xy} > \overline{yx}$”.

Quy tắc này hợp lệ vì có hàm khóa. Gọi $p$, $q$ là số chữ số của $x$, $y$; khi đó $\overline{xy} = x \cdot 10^q + y$ và $\overline{yx} = y \cdot 10^p + x$, nên

Vậy quy tắc chính là “khóa $f(x) = \frac{x}{10^p - 1}$ lớn hơn thì đứng trước”, với $10^p - 1$ là số gồm $p$ chữ số 9. Thứ tự đó cho kết quả lớn nhất: một cách xếp tối ưu không thể có cặp kề nào đổi chỗ được lợi, nên khóa không tăng từ trái sang phải.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
string s[10005];

bool cmp(string x, string y) {
    return x + y > y + x;
}

signed main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> s[i];
    sort(s + 1, s + n + 1, cmp);
    for (ll i = 1; i <= n; i++) cout << s[i];
    cout << '\n';
}

ChạyInput5
9 91 34 3 30

Output99134330

IVNén tọa độ

Nhiều bài cho giá trị cỡ $10^9$ nhưng chỉ cần biết cái nào nhỏ hơn, cái nào bằng nhau, trong khi ta lại muốn dùng giá trị làm chỉ số của mảng đếm hay cây Fenwick (bài 1.7). Khi đó thay mỗi giá trị bằng thứ hạng của nó trong tập giá trị phân biệt: nén tọa độ (coordinate compression). Phép thay giữ nguyên mọi quan hệ $<$ và $=$, nên bài chỉ dựa trên so sánh có cùng đáp án.

Ba bước: chép dãy ra, sắp, bỏ trùng bằng unique; thứ hạng của $x$ là vị trí của nó trong dãy đã bỏ trùng, tìm bằng lower_bound trong $O(\log n)$ (bài 0.6).

for (ll i = 1; i <= n; i++) v[i] = a[i];
sort(v + 1, v + n + 1);
ll m = unique(v + 1, v + n + 1) - v - 1;
for (ll i = 1; i <= n; i++) a[i] = lower_bound(v + 1, v + m + 1, a[i]) - v;

Sau đoạn trên các giá trị của $a$ nằm trong $[1, m]$. Với $a = (10^9, 5, 5, 42, 7, 10^9)$, các giá trị phân biệt $5, 7, 42, 10^9$ nhận hạng $1, 2, 3, 4$ và $a$ thành $(4, 1, 1, 3, 2, 4)$.