Sorting

Sắ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 B10). 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 06) hoặc chặt nhị phân (bài 05).

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. 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

Hà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

Sắp xếp trộn

Chọn, chèn, nổi bọt đều có hai vòng lặp lồng nhau và tốn $O(n^2)$. Với nổi bọt và chèn, lý do nằm ở nghịch thế. Nghịch thế (inversion) là cặp $i < j$ mà $a_i > a_j$; dãy giảm dần có $\frac{n(n-1)}{2}$ nghịch thế. Đổi chỗ hai phần tử kề nhau đang sai thứ tự xóa đúng một nghịch thế, nên thuật toán chỉ đổi chỗ phần tử kề nhau phải đổi ít nhất bằng số nghịch thế. Muốn nhanh hơn phải cho phần tử nhảy xa.

Sắp xếp trộn (merge sort) làm điều đó bằng cách chia đôi. Để sắp đoạn $[l, r]$: nếu chỉ có một phần tử thì xong; ngược lại đặt mid = (l + r) / 2 (chia nguyên), sắp đệ quy $[l, mid]$ và $[mid + 1, r]$, rồi trộn hai nửa bằng hai con trỏ, mỗi bước lấy ra số nhỏ hơn trong hai số đang trỏ: $(1, 4, 6, 9)$ trộn với $(2, 3, 7)$ cho $1, 2, 3, 4, 6, 7, 9$. Cách này đúng vì phần tử nhỏ nhất còn lại luôn nằm ở đầu một trong hai nửa.

Độ dài đoạn giảm một nửa sau mỗi tầng nên có khoảng $\log_2 n$ tầng; ở mỗi tầng các đoạn rời nhau và phủ cả mảng, trộn tốn thời gian tuyến tính, nên cả thuật toán tốn $O(n \log n)$. Với $n = 2 \cdot 10^5$ có 18 tầng.

Trong lúc trộn ta còn đếm được nghịch thế. Một nghịch thế nằm trọn trong nửa trái, trọn trong nửa phải, hoặc bắc qua hai nửa; hai loại đầu do hai lời gọi đệ quy đếm. Loại bắc qua đếm ngay lúc trộn: khi lấy $a_j$ của nửa phải ra, các phần tử nửa trái chưa lấy đều lớn hơn $a_j$ và đứng trước nó, nên có đúng mid - i + 1 nghịch thế mới, với i là con trỏ nửa trái. Hai số bằng nhau thì lấy bên trái trước, nên chúng không bị tính.

Còn câu hỏi cuối: có thuật toán nào nhanh hơn $n \log n$ không? Với các thuật toán chỉ dựa vào so sánh thì không. Dãy $n$ phần tử khác nhau có $n!$ thứ tự ban đầu, và mỗi thứ tự cần một cách sắp riêng. Mỗi phép so sánh chỉ trả lời “có” hoặc “không”, nên nhiều nhất chia đôi số khả năng còn lại; muốn phân biệt hết $n!$ khả năng thì cần khoảng $\log_2 n!$ phép so sánh, mà con số này cỡ $n \log_2 n$. Muốn nhanh hơn phải thôi so sánh, tức dùng thêm thông tin về giá trị.

Ví dụĐếm Cặp Ngược Thứ Tự

Đề. Dãy $N \le 2 \cdot 10^5$ số nguyên, $|a_i| \le 10^9$. Đếm số cặp $i < j$ với $a_i > a_j$ (bằng nhau không tính).

Lời giải. Sắp xếp trộn và cộng mid - i + 1 mỗi lần lấy phần tử nửa phải ra trước. Điều kiện lấy bên trái là a[i] <= a[j]: hai số bằng nhau lấy bên trái trước nên không bị đếm, đúng với dấu so sánh chặt của đề. Số nghịch thế tới $\frac{N(N-1)}{2} \approx 2 \cdot 10^{10}$, cần long long.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 2e5 + 5;
ll n, a[N], tmp[N];

ll solve(ll l, ll r) {
    if (l == r) return 0;
    ll mid = (l + r) >> 1;
    ll res = solve(l, mid) + solve(mid + 1, r);
    ll i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            res += mid - i + 1;
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r) tmp[k++] = a[j++];
    for (ll x = l; x <= r; x++) a[x] = tmp[x];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    cout << solve(1, n) << '\n';
}

ChạyInput4
3 1 2 1

Output4

Sắp xếp đếm

Có $n = 10^7$ số nguyên trong $[1, 10^4]$. std::sort cần cỡ $n \log_2 n \approx 2{,}3 \cdot 10^8$ phép so sánh, trong khi chỉ có $10^4$ giá trị khác nhau. Ta chỉ cần biết mỗi giá trị xuất hiện mấy lần: bảng đếm cnt[v], rồi viết $v$ ra đúng cnt[v] lần theo thứ tự tăng của $v$. Đó là sắp xếp đếm (counting sort), tốn $O(n + V)$ khi giá trị nằm trong $[0, V]$, không so sánh phần tử nào nên không vướng cận $n \log n$.

Sắp xếp đếm chỉ đi qua mảng hai lượt, mỗi lượt là phép cộng vào ô nhớ; std::sort phải so sánh và đổi chỗ cỡ $2 \cdot 10^8$ lần, chậm hơn khoảng 30 lần.

Khi mỗi phần tử còn mang dữ liệu khác (tên, chỉ số) và ta sắp theo một khóa nguyên nhỏ, cần bản ổn định. Lấy tổng tiền tố của bảng đếm (bài 02) để biết khối của mỗi khóa bắt đầu ở đâu, rồi duyệt đầu vào từ trái sang phải, đặt mỗi phần tử vào chỗ trống đầu tiên của khối khóa của nó. Phần tử đến trước nhận vị trí nhỏ hơn nên thứ tự giữa các phần tử cùng khóa được giữ nguyên.

for (ll i = 1; i <= n; i++) st[key[i] + 1]++;
st[0] = 1;
for (ll v = 1; v <= V + 1; v++) st[v] += st[v - 1];
for (ll i = 1; i <= n; i++) ord[st[key[i]]++] = i;

Sau đoạn trên ord[1..n] là các chỉ số theo khóa tăng dần, cùng khóa thì giữ thứ tự nhập. Tính ổn định còn cho phép sắp nhiều khóa bằng nhiều lượt: sắp theo khóa phụ trước, rồi sắp ổn định theo khóa chính; áp dụng với các “chữ số” từ thấp lên cao ta được sắp xếp theo cơ số (radix sort).

Sắp xếp đếm đáng dùng khi $V$ cỡ $n$ trở xuống. Với giá trị tới $10^9$, bảng đếm cần $10^9$ ô; khi đó dùng std::sort, hoặc nén tọa độ ở mục cuối nếu chỉ cần thứ tự.

Ví dụDãy Số Theo Thứ Tự Tăng

Đề. $n \le 10^7$ số nguyên dương $a_i \le 10^4$, mỗi số một dòng. In dãy sau khi sắp không giảm, mỗi số một dòng.

Lời giải. Giá trị nhỏ còn $n$ rất lớn: đếm cnt[v] rồi in $v$ đúng cnt[v] lần, $O(n + 10^4)$. Phần tính toán chỉ là vài dòng; phần chậm nhất lại là đọc và ghi, vì đầu vào cỡ 60 MB và đầu ra cũng vậy. Ngay cả cin đã tắt đồng bộ cũng mất cỡ một giây cho $10^7$ số, nên ta tự làm việc đọc ghi theo từng khối lớn. Lời giải gồm bốn phần.

Bước 1: đọc theo khối. fread chép một lần $2^{16}$ byte từ đầu vào vào mảng ibuf; gc() trả về từng ký tự trong khối đó và chỉ gọi fread lại khi đã dùng hết. Hết dữ liệu thì fread trả về 0 và gc() trả về ký tự 0.

char gc() {
    if (ip == il) {
        il = fread(ibuf, 1, sizeof ibuf, stdin);
        ip = 0;
        if (il == 0) return 0;
    }
    return ibuf[ip++];
}

Bước 2: tách số. read() bỏ qua mọi ký tự đứng trước '0' trong bảng mã, tức dấu cách và xuống dòng, rồi ghép các chữ số thành một số như ở bài B1 (nhân 10 rồi cộng chữ số mới). Đề chỉ có số dương nên không cần lo dấu trừ.

ll read() {
    char c = gc();
    while (c < '0') c = gc();
    ll x = 0;
    while (c >= '0') {
        x = x * 10 + c - '0';
        c = gc();
    }
    return x;
}

Bước 3: ghi qua bộ đệm. put(c) thêm một ký tự vào obuf; đầy thì đẩy cả khối ra bằng fwrite. Cuối main còn một lần fwrite cho phần dư.

void put(char c) {
    if (op == sizeof obuf) {
        fwrite(obuf, 1, op, stdout);
        op = 0;
    }
    obuf[op++] = c;
}

Bước 4: đếm rồi in. Đọc $n$ số vào bảng đếm. Duyệt $v$ từ 1 tới $10^4$, đổi $v$ thành xâu một lần bằng to_string, rồi ghi xâu đó cnt[v] lần. Thứ tự tăng của $v$ cho thứ tự không giảm của dãy.

n = read();
for (ll i = 1; i <= n; i++) cnt[read()]++;
for (ll v = 1; v <= 10000; v++) {
    string s = to_string(v);
    for (ll k = 1; k <= cnt[v]; k++) {
        for (char c : s) put(c);
        put('\n');
    }
}
fwrite(obuf, 1, op, stdout);

Ghép bốn phần lại:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, cnt[10005];
char ibuf[1 << 16], obuf[1 << 16];
ll ip, il, op;

char gc() {
    if (ip == il) {
        il = fread(ibuf, 1, sizeof ibuf, stdin);
        ip = 0;
        if (il == 0) return 0;
    }
    return ibuf[ip++];
}

ll read() {
    char c = gc();
    while (c < '0') c = gc();
    ll x = 0;
    while (c >= '0') {
        x = x * 10 + c - '0';
        c = gc();
    }
    return x;
}

void put(char c) {
    if (op == sizeof obuf) {
        fwrite(obuf, 1, op, stdout);
        op = 0;
    }
    obuf[op++] = c;
}

signed main() {
    n = read();
    for (ll i = 1; i <= n; i++) cnt[read()]++;
    for (ll v = 1; v <= 10000; v++) {
        string s = to_string(v);
        for (ll k = 1; k <= cnt[v]; k++) {
            for (char c : s) put(c);
            put('\n');
        }
    }
    fwrite(obuf, 1, op, stdout);
}

ChạyInput8
4
1
4
2
10000
2
1
7

Output1
1
2
2
4
4
7
10000

Mỗi số được đọc một lần và in một lần, cộng $10^4$ bước duyệt bảng đếm: $O(n + V)$ thời gian, $O(V)$ bộ nhớ ngoài hai bộ đệm.

Tự 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 04.

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

Né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 16). 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 05).

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)$.