Tham lam với hàng đợi ưu tiên

Rất nhiều bài tham lam có chung một khuôn: quét dữ liệu theo một chiều (thời gian, hạn chót, tọa độ), giữ các ứng viên đang "còn hiệu lực" trong một hàng đợi ưu tiên (heap), và mỗi khi cần quyết định thì lấy ứng viên tốt nhất (hoặc vứt ứng viên tệ nhất) ra khỏi heap. Nhờ heap, mỗi quyết định chỉ tốn $O(\log N)$ nên cả thuật toán chạy trong $O(N\log N)$, thay vì $O(N^2)$ khi mỗi bước phải dò lại toàn bộ ứng viên, hoặc $O(2^N)$ khi thử mọi tập con.

Trang này đi sâu vào năm dạng kinh điển: lập lịch có hạn chót, tham lam "hối hận" (đổi ý), gộp dần hai phần tử nhỏ nhất (Huffman), số phòng tối thiểu và ghép đoạn với điểm, duyệt $k$ trạng thái nhỏ nhất bằng heap, cùng hai kỹ thuật phụ trợ là xóa lười (lazy deletion) và hai heap giữ trung vị. Nền tảng về tham lam và lập luận trao đổi xem ở Tham lam; cách heap hoạt động bên trong xem ở Heap.

Ý tưởng chung: quét một chiều, heap giữ ứng viên

Mọi bài trong trang này đều trả lời ba câu hỏi:

1. Quét theo chiều nào? Thường là sắp xếp theo hạn chót, theo thời điểm bắt đầu, hoặc đơn giản là đi theo thứ tự ngày.
2. Heap chứa gì? Các ứng viên đã "mở" (đã được quét qua, còn dùng được) nhưng chưa được quyết định dứt điểm.
3. Khi nào lấy ra, lấy cái nào? Lấy ứng viên tốt nhất khi có một "chỗ" cần lấp, hoặc bỏ ứng viên tệ nhất khi tập đang giữ vi phạm ràng buộc.

sắp xếp / quét theo một chiều
for mỗi phần tử x theo thứ tự quét:
    đưa x (và mọi ứng viên vừa mở) vào heap
    while ràng buộc bị vi phạm:        # hoặc: if có chỗ cần lấp
        lấy phần tử ở đỉnh heap ra     # tệ nhất để bỏ, hoặc tốt nhất để dùng

Điều làm cách này đúng luôn là một lập luận trao đổi: tại thời điểm quyết định, ứng viên ở đỉnh heap là lựa chọn "an toàn nhất", vì bất kỳ lời giải tối ưu nào chọn khác đều có thể tráo sang lựa chọn đó mà không tệ đi. Điều làm cách này nhanh là heap: tìm và lấy ra phần tử tốt nhất trong $O(\log N)$.

Dạng 1: Lập lịch có hạn chót

Bài toán. Có $N$ việc, mỗi việc làm mất đúng $1$ đơn vị thời gian, việc $i$ phải xong trước hoặc đúng thời điểm $d_i$ (tức là phải được xếp vào một trong các ô thời gian $1,2,\dots ,d_i$) và đem lại lợi nhuận $p_i\ge 0$ nếu làm đúng hạn. Chọn tập việc để tổng lợi nhuận lớn nhất.

Ý tưởng

Tập việc $S$ làm được đúng hạn khi và chỉ khi xếp chúng theo hạn chót tăng dần thì việc thứ $k$ có hạn $\ge k$. Tương đương: với mọi $t$, số việc trong $S$ có hạn $\le t$ không vượt quá $t$. Gọi tập như vậy là khả thi.

Quét các việc theo hạn chót tăng dần, giữ tập việc đang chọn trong một min-heap theo lợi nhuận:

• Thêm việc mới vào heap.
• Nếu số việc trong heap vượt quá hạn chót hiện tại $d$ thì tập không còn khả thi (có $d+1$ việc cùng phải xong trước $d$). Bỏ việc có lợi nhuận nhỏ nhất.

Vì sao đúng (lập luận trao đổi). Gọi $H$ là heap trước khi xét việc mới $j$ có hạn $d$; mọi việc đã xét đều có hạn $\le d$. Ta giữ hai bất biến:

• (A) heap luôn là một tập khả thi;
• (B) tồn tại một lời giải tối ưu $OPT$ của toàn bộ bài toán không chứa việc nào đã bị bỏ.

Giữ (A). $H$ khả thi và mọi việc trong $H$ có hạn $\le d$ nên $|H|\le d$. Gọi $H^{\prime }$ là heap sau bước này ($H\cup \{j\}$, có thể bớt một việc). Với $t<d$: các việc có hạn $\le t$ trong $H^{\prime }$ đều thuộc $H$ (vì $j$ có hạn $d$), nên số lượng không quá $t$ nhờ $H$ khả thi. Với $t\ge d$: mọi việc của $H^{\prime }$ đều được đếm, và $|H^{\prime }|\le d\le t$ (nếu $|H|+1>d$ thì ta đã bỏ một việc để còn đúng $d$).

Giữ (B). Chỉ cần xét bước có bỏ việc: lúc đó $|H\cup \{j\}|=d+1$ và ta bỏ việc rẻ nhất $x$. Nếu $x\notin OPT$ thì xong. Nếu $x\in OPT$: $OPT$ khả thi nên không chứa được cả $d+1$ việc có hạn $\le d$, vậy có $y\in H\cup \{j\}$ mà $y\notin OPT$, và $p_y\ge p_x$. Đặt $OP{T}^{\prime }=OPT-x+y$, tổng lợi nhuận không giảm. $OP{T}^{\prime }$ vẫn khả thi:

• Với $t\ge d$: cả $x$ lẫn $y$ đều có hạn $\le d\le t$, nên số việc có hạn $\le t$ trong $OP{T}^{\prime }$ đúng bằng trong $OPT$, không đổi.
• Với $t<d$: các việc có hạn $\le t$ đều đã được xét; theo (B) chúng không nằm trong số việc bị bỏ trước đó, $x$ đã bị loại khỏi $OP{T}^{\prime }$, còn $j$ có hạn $d>t$. Vậy các việc có hạn $\le t$ của $OP{T}^{\prime }$ nằm trong $H$ cũ, và $H$ khả thi nên có không quá $t$ việc như vậy.

Rủi ro thật nằm ở các ô trước $d$ ($y$ có thể có hạn nhỏ hơn $x$), và chính tính khả thi của heap cũ chặn được rủi ro đó. Cuối cùng, theo (B) có một $OPT$ nằm gọn trong heap cuối; heap cuối khả thi theo (A) và mọi lợi nhuận không âm nên tổng của heap cuối không nhỏ hơn tổng của $OPT$, tức là tối ưu.

Trực giác: mỗi khi "chật chỗ", việc bị hy sinh phải là việc kém giá trị nhất trong số những việc đang tranh nhau chỗ. Bất biến (B) nói rằng việc đã bị bỏ thì không bao giờ cần lấy lại, vì các việc đến sau có hạn muộn hơn, chỉ làm cuộc tranh chấp gay gắt hơn chứ không nới lỏng. (Về bản chất, các tập khả thi tạo thành một matroid, nên tham lam theo lợi nhuận luôn đúng.)

Ví dụ chạy tay

Việc:        A    B    C    D    E
hạn d:       2    1    2    1    3
lợi p:      50   10   20   40   30

Sắp theo $(d,p)$: B(1,10), D(1,40), C(2,20), A(2,50), E(3,30). Heap in từ nhỏ đến lớn.

bước  xét           heap sau khi thêm      |heap| > d ?     heap sau khi bỏ    tổng
 1    B  d=1 p=10   [10]                   1 > 1  không     [10]               10
 2    D  d=1 p=40   [10 40]                2 > 1  CÓ  bỏ 10 [40]               40
 3    C  d=2 p=20   [20 40]                2 > 2  không     [20 40]            60
 4    A  d=2 p=50   [20 40 50]             3 > 2  CÓ  bỏ 20 [40 50]            90
 5    E  d=3 p=30   [30 40 50]             3 > 3  không     [30 40 50]        120

Lịch cuối:   ô 1    ô 2    ô 3
             D      A      E        tổng lợi nhuận = 40 + 50 + 30 = 120

Để ý bước 4: C đã được giữ ở bước 3 nhưng bị "đá" ra khi A (đắt hơn, cùng hạn) xuất hiện. Heap cho phép sửa lại quyết định cũ với chi phí $O(\log N)$.

Cài đặt

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

// Unit-time jobs: job i must be done in a slot 1..d[i], giving profit p[i].
// Maximize the total profit of the jobs done on time.
long long maxProfit(vector<pair<int,long long>> jobs) {   // {deadline, profit}
    sort(jobs.begin(), jobs.end());                       // scan by deadline
    priority_queue<long long, vector<long long>, greater<long long>> chosen; // min-heap of profits
    long long total = 0;
    for (auto [d, p] : jobs) {
        chosen.push(p);
        total += p;
        if ((int)chosen.size() > d) {        // more jobs than slots 1..d
            total -= chosen.top();            // drop the least profitable one
            chosen.pop();
        }
    }
    return total;
}

int main() {
    int n;
    cin >> n;
    vector<pair<int,long long>> jobs(n);
    for (auto& [d, p] : jobs) cin >> d >> p;
    cout << maxProfit(jobs) << "\n";
}

Biến thể: việc có độ dài khác nhau, tối đa số việc (Moore-Hodgson)

Việc $i$ tốn $t_i$ thời gian và phải xong trước $d_i$; cần làm nhiều việc nhất. Quét theo hạn chót, giữ max-heap theo độ dài; nếu tổng thời gian vượt hạn chót hiện tại thì bỏ việc dài nhất. Lý do: mọi việc đều đáng "1 điểm", nên khi buộc phải bỏ một việc, bỏ việc chiếm nhiều thời gian nhất sẽ để lại nhiều chỗ nhất cho các việc sau.

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

// Job: {deadline, duration}. Maximize the number of jobs finished on time.
int maxJobs(vector<pair<long long,long long>> jobs) {
    sort(jobs.begin(), jobs.end());                      // scan by deadline
    priority_queue<long long> durations;                 // max-heap of chosen durations
    long long busy = 0;                                  // total time of chosen jobs
    for (auto [d, t] : jobs) {
        durations.push(t);
        busy += t;
        if (busy > d) {                  // the new set is late: drop the longest job
            busy -= durations.top();
            durations.pop();
        }
    }
    return durations.size();
}

int main() {
    int n;
    cin >> n;
    vector<pair<long long,long long>> jobs(n);
    for (auto& [d, t] : jobs) cin >> d >> t;   // deadline, duration
    cout << maxJobs(jobs) << "\n";
}

Chỉ cần bỏ một việc mỗi lần: trước khi thêm, tập đang giữ khả thi, và việc bị bỏ dài ít nhất bằng việc vừa thêm, nên sau khi bỏ tổng thời gian không vượt mức trước đó.

Dạng 2: Tham lam hối hận (regret greedy)

Đôi khi một quyết định trông tốt lúc này nhưng về sau lại hóa dở. Thay vì quay lui, ta đẩy vào heap một "vé hoàn tác": một phần tử mà nếu sau này được chọn thì hiệu quả của nó đúng bằng việc hủy quyết định cũ và làm một quyết định tốt hơn.

Bài toán (dạng CF 865D). Biết trước giá cổ phiếu $N$ ngày. Mỗi ngày được mua một cổ phiếu, bán một cổ phiếu, hoặc không làm gì; không được bán khi không có cổ phiếu. Tối đa lợi nhuận.

Ý tưởng

Duyệt từng ngày với giá $p$, giữ min-heap các "giá mua ứng viên":

• Nếu đỉnh heap $c<p$: bán hôm nay với giá $p$ ghép với lần mua giá $c$, lời $p-c$. Lấy $c$ ra, và đẩy $p$ vào heap làm vé hoàn tác.
• Luôn đẩy $p$ vào heap như một ngày có thể mua.

Vì sao vé hoàn tác đúng? Giả sử về sau có ngày giá $q>p$ ghép với vé $p$, ta cộng thêm $q-p$. Tổng hai lần là $(p-c)+(q-p)=q-c$: đúng bằng mua ở $c$, bán ở $q$, còn ngày $p$ trở thành ngày trống. Như vậy thuật toán được phép "đổi ý" về ngày bán mà không cần quay lui. Hai bản sao của $p$ có cùng giá trị, bản được dùng trước luôn được hiểu là vé hoàn tác, bản dùng sau (nếu có) mới là một lần mua thật ở ngày $p$ (lúc đó ngày $p$ đã trống).

Ví dụ chạy tay

Giá $=[1,3,5,2,6]$.

ngày  giá  đỉnh heap   hành động                       heap sau (tăng dần)   lợi nhuận
 1     1   (rỗng)      chỉ đẩy 1                       [1]                     0
 2     3   1 < 3       bán 3 ghép 1 (+2), đẩy vé 3     [3 3]                   2
 3     5   3 < 5       bán 5 ghép vé 3 (+2), đẩy vé 5  [3 5 5]                 4
 4     2   3 > 2       không bán, đẩy 2                [2 3 5 5]               4
 5     6   2 < 6       bán 6 ghép 2 (+4), đẩy vé 6     [3 5 5 6 6]             8

Ở ngày 3, việc "bán 5 ghép vé 3" thực chất là hủy lần bán ở ngày 2 và chuyển sang bán ở ngày 3. Giao dịch thật: mua 1 bán 5, mua 2 bán 6, lợi nhuận $4+4=8$.

Cài đặt

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

// Each day: buy one share, sell one share, or do nothing. Maximize profit.
long long maxStockProfit(const vector<long long>& price) {
    priority_queue<long long, vector<long long>, greater<long long>> cand; // min-heap of buy prices
    long long profit = 0;
    for (long long p : price) {
        if (!cand.empty() && cand.top() < p) {
            profit += p - cand.top();   // sell today against the cheapest candidate
            cand.pop();
            cand.push(p);               // regret ticket: this sale may move to a later day
        }
        cand.push(p);                   // today is also a plain buy candidate
    }
    return profit;
}

int main() {
    int n;
    cin >> n;
    vector<long long> price(n);
    for (auto& x : price) cin >> x;
    cout << maxStockProfit(price) << "\n";
}

Cùng tư tưởng "đẩy lại để còn đổi ý" là cốt lõi của Slope Trick: ở đó mỗi phần tử được đẩy hai lần vào heap điểm gãy, và việc lấy đỉnh ra chính là sửa lại giá trị đã chọn trước đó.

Dạng 3: Gộp dần hai phần tử nhỏ nhất (Huffman, nối dây)

Bài toán. Có $N$ đống (hoặc $N$ sợi dây) khối lượng $a_i$. Mỗi lần gộp hai đống với chi phí bằng tổng khối lượng của chúng, được một đống mới. Gộp tất cả thành một đống với tổng chi phí nhỏ nhất.

Vì sao luôn gộp hai đống nhỏ nhất

Vẽ quá trình gộp thành một cây nhị phân: lá là các đống ban đầu, mỗi nút trong là một lần gộp. Một đống ban đầu nằm ở độ sâu $h_i$ thì bị cộng vào chi phí đúng $h_i$ lần, nên

$$\text{chi phí}=\sum _i{a}_i·h_i.$$

• Trong một cây tối ưu, nút sâu nhất luôn có anh em (nếu không, kéo nó lên thay cha sẽ giảm chi phí).
• Hai đống nhỏ nhất $x\le y$ có thể được đặt làm hai lá anh em ở độ sâu lớn nhất: nếu một lá sâu nhất là $z>x$, tráo $x$ với $z$ thay đổi chi phí một lượng $(x-z)(h_{max}-h_x)\le 0$, không tệ đi.
• Gộp $x,y$ trước thì bài toán còn lại là bài cùng dạng với $N-1$ đống (đống $x+y$ thay cho hai đống), cộng chi phí cố định $x+y$. Quy nạp cho ra thuật toán.

Ví dụ chạy tay

heap: [1 2 5 9]
  lấy 1, 2  -> gộp 3  (chi phí 3)    heap: [3 5 9]
  lấy 3, 5  -> gộp 8  (chi phí 8)    heap: [8 9]
  lấy 8, 9  -> gộp 17 (chi phí 17)   heap: [17]
tổng = 3 + 8 + 17 = 28

cây gộp:        17
               /  \
              8    9          độ sâu: 1,2 ở mức 3; 5 ở mức 2; 9 ở mức 1
             / \              1*3 + 2*3 + 5*2 + 9*1 = 28
            3   5
           / \
          1   2

Cài đặt

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

int main() {
    int n;
    cin >> n;
    priority_queue<long long, vector<long long>, greater<long long>> pq; // min-heap
    for (int i = 0; i < n; i++) { long long x; cin >> x; pq.push(x); }
    long long cost = 0;
    while (pq.size() > 1) {
        long long x = pq.top(); pq.pop();   // two smallest piles
        long long y = pq.top(); pq.pop();
        cost += x + y;
        pq.push(x + y);                     // merged pile is a new candidate
    }
    cout << cost << "\n";
}

Mẹo $O(N)$ sau khi sắp xếp: các đống mới sinh ra có khối lượng không giảm, nên có thể thay heap bằng hai hàng đợi thường (một chứa đống ban đầu đã sắp, một chứa đống vừa gộp) và mỗi lần lấy phần tử nhỏ hơn ở hai đầu hàng.

Dạng 4: Số phòng tối thiểu và ghép đoạn với điểm

Số phòng (số máy) tối thiểu

Bài toán. Khách $i$ ở trong khoảng ngày $[a_i,b_i]$. Hai khách ở chung phòng được nếu khách trước rời đi thực sự sớm hơn ngày khách sau đến. Tìm số phòng ít nhất và gán phòng cho từng khách.

Ý tưởng. Quét khách theo ngày đến tăng dần, giữ min-heap các ngày rời đi của những phòng đang có khách. Với khách mới, phòng có ngày rời sớm nhất là phòng có khả năng trống nhất: nếu nó trống thì dùng lại, nếu nó còn bận thì mọi phòng đều bận, buộc phải mở phòng mới.

Vì sao tối ưu. Khi phải mở phòng thứ $k$ cho khách $i$, cả $k-1$ phòng cũ đều có khách còn ở tại ngày $a_i$, cùng với khách $i$ là $k$ người cùng có mặt ở ngày $a_i$. Mọi cách xếp đều cần ít nhất $k$ phòng. Vậy số phòng của thuật toán bằng đúng số khoảng chồng nhau lớn nhất tại một thời điểm, là cận dưới.

Ví dụ: khách 1 $[1,3]$, khách 2 $[2,5]$, khách 3 $[4,6]$, khách 4 $[3,4]$.

ngày:        1   2   3   4   5   6
khách 1:     [=======]                phòng 1
khách 2:         [===========]        phòng 2
khách 4:             [===]            phòng 3  (khách 1 rời ngày 3, không < 3)
khách 3:                 [=======]    phòng 1  (khách 1 rời ngày 3 < 4)

xét theo ngày đến     đỉnh heap (rời, phòng)   quyết định
khách 1 (a=1)         rỗng                     mở phòng 1
khách 2 (a=2)         (3, P1): 3 < 2 ? không   mở phòng 2
khách 4 (a=3)         (3, P1): 3 < 3 ? không   mở phòng 3
khách 3 (a=4)         (3, P1): 3 < 4 ? có      dùng lại phòng 1
đáp số: 3 phòng (ngày 3 có khách 1, 2, 4 cùng ở)

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

int main() {
    int n;
    cin >> n;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; i++) cin >> a[i] >> b[i];
    vector<int> order(n);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [&](int x, int y) { return a[x] < a[y]; });

    // min-heap of {leave day, room id} for occupied rooms
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> busy;
    vector<int> room(n);
    int rooms = 0;
    for (int i : order) {
        if (!busy.empty() && busy.top().first < a[i]) {  // earliest-free room is free now
            room[i] = busy.top().second;
            busy.pop();
        } else {
            room[i] = ++rooms;                             // every room is busy: open one
        }
        busy.push({b[i], room[i]});
    }
    cout << rooms << "\n";
    for (int i = 0; i < n; i++) cout << room[i] << " \n"[i == n - 1];
}

Ghép đoạn với điểm

Bài toán. Có các đoạn $[l_i,r_i]$ và các điểm nguyên $1..M$. Mỗi điểm cấp cho tối đa một đoạn, mỗi đoạn cần một điểm nằm trong nó. Có cấp đủ cho mọi đoạn không?

Quét điểm $p=1,2,\dots ,M$. Đưa vào min-heap theo đầu phải mọi đoạn có $l=p$. Tại điểm $p$, cấp $p$ cho đoạn gấp nhất (đầu phải nhỏ nhất). Nếu đoạn gấp nhất đã có $r<p$ thì nó đã lỡ, không còn cách nào.

Trao đổi: giả sử một cách ghép hợp lệ cấp $p$ cho đoạn $J$ trong khi đoạn gấp nhất $I$ (có $r_I\le r_J$) nhận điểm $q>p$. Tráo: $I$ nhận $p$, $J$ nhận $q$. Vì $l_J\le p<q\le r_I\le r_J$ nên $q$ nằm trong $J$, cách ghép vẫn hợp lệ. (Nếu $I$ không được cấp điểm nào thì cho $I$ lấy $p$ thay $J$, số đoạn được cấp không giảm.)

Chương trình dưới đọc $n$, $M$ rồi $n$ đoạn, in YES nếu cấp đủ và NO nếu không.

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

// Can every interval [l, r] (1 <= l <= r <= M) get its own distinct integer point?
bool canMatch(const vector<pair<int,int>>& seg, int M) {
    vector<vector<int>> startAt(M + 2);
    for (auto [l, r] : seg) startAt[l].push_back(r);
    priority_queue<int, vector<int>, greater<int>> openEnds;   // right ends of waiting intervals
    for (int p = 1; p <= M; p++) {
        for (int r : startAt[p]) openEnds.push(r);
        if (openEnds.empty()) continue;
        if (openEnds.top() < p) return false;   // it expired without a point
        openEnds.pop();                          // point p goes to the most urgent interval
    }
    return openEnds.empty();                     // leftovers were never served
}

int main() {
    int n, M;
    cin >> n >> M;
    vector<pair<int,int>> seg(n);
    for (auto& [l, r] : seg) cin >> l >> r;
    cout << (canMatch(seg, M) ? "YES" : "NO") << "\n";
}

⚠️ Chọn đoạn mở sớm nhất (đầu trái nhỏ nhất) là sai: đoạn $[1,10]$ mở sớm nhưng không gấp, cấp điểm $1$ cho nó có thể làm đoạn $[1,1]$ mất chỗ. Hàm kiểm tra này thường được bọc trong tìm kiếm nhị phân theo đáp số khi đề hỏi "giá trị nhỏ nhất để ghép được".

Dạng 5: Duyệt $k$ trạng thái nhỏ nhất bằng heap

Khi không gian lời giải rất lớn (ví dụ $N·M$ tổng $a_i+b_j$) nhưng chỉ cần $k$ giá trị nhỏ nhất, ta không sinh hết. Thay vào đó, xem mỗi lời giải là một trạng thái, và thiết kế phép "trạng thái kế tiếp" sao cho:

• trạng thái kế tiếp không nhỏ hơn trạng thái hiện tại;
• mỗi trạng thái được sinh ra đúng một lần (từ đúng một trạng thái cha).

Heap giữ "biên" của vùng đã khám phá. Mỗi lần lấy ra trạng thái nhỏ nhất rồi đẩy các trạng thái kế tiếp của nó. Giống như Dijkstra, trạng thái được lấy ra lần thứ $t$ chính là trạng thái nhỏ thứ $t$.

$k$ tổng nhỏ nhất của hai dãy đã sắp. Xem bảng $a_i+b_j$: mỗi hàng $i$ tăng dần theo $j$. Khởi tạo heap bằng ô đầu mỗi hàng $(i,0)$; khi lấy ra $(i,j)$ thì chỉ đẩy $(i,j+1)$. Mỗi ô có đúng một cha nên không trùng lặp.

a = [1 7 11], b = [2 4 6], k = 5

            b: 2     4     6
a = 1:        3     5     7
a = 7:        9    11    13
a = 11:      13    15    17

lấy  (tổng, i, j)   đẩy thêm      heap sau
 1   (3, 0, 0)      (5, 0, 1)     {5, 9, 13}
 2   (5, 0, 1)      (7, 0, 2)     {7, 9, 13}
 3   (7, 0, 2)      (hết hàng)    {9, 13}
 4   (9, 1, 0)      (11, 1, 1)    {11, 13}
 5   (11, 1, 1)     ...
kết quả: 3 5 7 9 11

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

// k smallest values of a[i] + b[j], with a and b sorted ascending, k <= |a| * |b|.
vector<long long> kSmallestSums(const vector<long long>& a, const vector<long long>& b, int k) {
    using State = tuple<long long,int,int>;               // {sum, i, j}
    priority_queue<State, vector<State>, greater<State>> pq;
    for (int i = 0; i < (int)a.size() && i < k; i++) pq.push({a[i] + b[0], i, 0});
    vector<long long> res;
    while ((int)res.size() < k) {
        auto [s, i, j] = pq.top(); pq.pop();
        res.push_back(s);
        if (j + 1 < (int)b.size()) pq.push({a[i] + b[j + 1], i, j + 1}); // only successor in row i
    }
    return res;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<long long> a(n), b(m);
    for (auto& x : a) cin >> x;
    for (auto& x : b) cin >> x;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (long long s : kSmallestSums(a, b, k)) cout << s << " ";
    cout << "\n";
}

Cùng khuôn đó giải được:

• $k$ phần tử nhỏ nhất từ $m$ dãy đã sắp (trộn $m$ dãy): heap giữ phần tử đầu của mỗi dãy, lấy ra phần tử của dãy nào thì đẩy phần tử tiếp theo của dãy đó. Mỗi phần tử tốn $O(\log m)$.
• $k$ tổng nhỏ nhất của $m$ dãy đã sắp (chọn một phần tử mỗi dãy): trạng thái là vectơ chỉ số $(j_1,\dots ,j_m)$, gốc là $(0,\dots ,0)$ (tổng các phần tử đầu). Để tránh trùng, quy định cha của một trạng thái khác gốc là trạng thái thu được khi giảm $1$ ở vị trí khác $0$ cuối cùng. Gốc không có vị trí khác $0$ nào nên xét riêng: các con của gốc là đặt một $j_u$ bất kỳ từ $0$ lên $1$. Với trạng thái khác gốc có vị trí khác $0$ cuối cùng là $t$, các con gồm: tăng $j_t$ thêm $1$, hoặc tăng một $j_u$ với $u>t$ từ $0$ lên $1$. Mỗi trạng thái có đúng một cha và con không bao giờ nhỏ hơn cha; để sinh con chỉ cần lưu (tổng, $t$, $j_t$), không phải lưu cả vectơ. Mỗi lần lấy ra có thể đẩy tới $m$ con, nên độ phức tạp là $O(k·m·\log (km))$ chứ không phải $O(k\log k)$. Muốn nhanh hơn, tách riêng các dãy chỉ có một phần tử (chúng chỉ cộng hằng số) rồi sắp các dãy còn lại theo độ chênh $a_u[1]-a_u[0]$ tăng dần; khi đó gốc chỉ có một con là đặt $j_1=1$, và mỗi trạng thái khác chỉ cần ba con: tăng $j_t$; đặt $j_{t+1}=1$; và nếu $j_t=1$ thì "dời" (đưa $j_t$ về $0$, đặt $j_{t+1}=1$), nhờ thứ tự đã sắp mà phép dời không làm tổng giảm. Mỗi lần lấy ra đẩy tối đa $3$ con, tổng còn $O(m\log m+k\log k)$.

Xóa lười và hai heap giữ trung vị

Xóa lười (lazy deletion)

priority_queue chỉ xóa được phần tử ở đỉnh. Khi cần xóa một phần tử bất kỳ, ta đánh dấu nó (ví dụ tăng delayed[x]) và chỉ thật sự vứt nó đi khi nó nổi lên đỉnh. Quy tắc:

• Trước mỗi lần đọc top(), gọi prune() để bỏ các phần tử đã bị đánh dấu ở đỉnh.
• Kích thước thật không phải size() của heap, phải tự đếm số phần tử còn hiệu lực.

Dijkstra dùng đúng kỹ thuật này dưới dạng if (d > dist[u]) continue; (xem Dijkstra). Tổng chi phí vẫn là $O(\log N)$ khấu hao mỗi thao tác, vì mỗi phần tử bị đẩy vào một lần thì bị lấy ra nhiều nhất một lần.

Hai heap giữ trung vị

Chia tập hiện tại làm hai nửa: max-heap lo giữ nửa nhỏ, min-heap hi giữ nửa lớn, luôn giữ $|lo|=|hi|$ hoặc $|lo|=|hi|+1$. Khi đó trung vị (phần tử giữa, lấy phần tử nhỏ hơn khi số lượng chẵn) là lo.top().

tập {1, 2, 3, 5, 8}:   lo (max-heap) = {1 2 3}  -> top 3 = trung vị
                       hi (min-heap) = {5 8}
thêm 4:  4 > lo.top()=3 nên vào hi = {4 5 8}; |lo| = |hi| = 3, trung vị vẫn 3
thêm 0:  vào lo = {0 1 2 3}; |lo| = 4 > |hi| + 1 ? không (4 = 3 + 1), trung vị 3

Kết hợp với xóa lười, ta có trung vị cửa sổ trượt: mỗi bước thêm phần tử mới vào và xóa phần tử rời cửa sổ.

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

// Sliding-window median: two heaps + lazy deletion.
// lo (max-heap) holds the smaller half, hi (min-heap) the larger half; median = lo.top().
struct DualHeap {
    priority_queue<int> lo;
    priority_queue<int, vector<int>, greater<int>> hi;
    unordered_map<int,int> delayed;   // value -> pending deletions
    int loSize = 0, hiSize = 0;       // number of VALID elements in each heap

    template <class Heap> void prune(Heap& h) {    // drop stale tops
        while (!h.empty()) {
            auto it = delayed.find(h.top());
            if (it == delayed.end() || it->second == 0) break;
            it->second--;
            h.pop();
        }
    }
    void rebalance() {                // keep loSize == hiSize or loSize == hiSize + 1
        if (loSize > hiSize + 1) {
            hi.push(lo.top()); lo.pop(); loSize--; hiSize++; prune(lo);
        } else if (loSize < hiSize) {
            lo.push(hi.top()); hi.pop(); hiSize--; loSize++; prune(hi);
        }
    }
    void insert(int x) {
        if (lo.empty() || x <= lo.top()) { lo.push(x); loSize++; }
        else { hi.push(x); hiSize++; }
        rebalance();
    }
    void erase(int x) {               // x must currently be in the window
        delayed[x]++;
        if (x <= lo.top()) { loSize--; if (x == lo.top()) prune(lo); }
        else { hiSize--; if (!hi.empty() && x == hi.top()) prune(hi); }
        rebalance();
    }
    int median() { return lo.top(); }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    DualHeap dh;
    for (int i = 0; i < n; i++) {
        dh.insert(a[i]);
        if (i >= k) dh.erase(a[i - k]);           // insert first so the window is never empty
        if (i >= k - 1) cout << dh.median() << " \n"[i == n - 1];
    }
}

Với $a=[2,4,3,5,8,1,2,1]$, $k=3$, chương trình in 3 4 5 5 2 1. Nếu ngại cài xóa lười, có thể thay hai heap bằng hai multiset (xóa trực tiếp bằng erase(find(x))), chậm hơn một chút nhưng khó sai hơn.

Cài đặt Python (heapq)

heapq chỉ có min-heap trên một list. Muốn max-heap thì đẩy số đối ($-x$). Hàm heapreplace(h, x) lấy phần tử nhỏ nhất ra rồi đẩy $x$ vào trong một bước, rất hợp với tham lam hối hận.

import heapq

def max_profit(jobs):
    """jobs: list of (deadline, profit); each job takes one time unit."""
    chosen = []                          # min-heap of chosen profits
    for d, p in sorted(jobs):
        heapq.heappush(chosen, p)
        if len(chosen) > d:
            heapq.heappop(chosen)        # drop the least profitable job
    return sum(chosen)

def max_stock_profit(prices):
    cand, profit = [], 0                 # min-heap of buy candidates
    for p in prices:
        if cand and cand[0] < p:
            profit += p - heapq.heapreplace(cand, p)  # pop cheapest, push regret ticket p
        heapq.heappush(cand, p)
    return profit

def merge_cost(a):
    heapq.heapify(a)                     # O(N) build
    cost = 0
    while len(a) > 1:
        s = heapq.heappop(a) + heapq.heappop(a)
        cost += s
        heapq.heappush(a, s)
    return cost

print(max_profit([(2, 50), (1, 10), (2, 20), (1, 40), (3, 30)]))  # 120
print(max_stock_profit([1, 3, 5, 2, 6]))                           # 8
print(merge_cost([1, 2, 5, 9]))                                    # 28

Độ phức tạp

Điểm chung: số thao tác heap tỉ lệ với số lần một phần tử được đẩy vào, vì mỗi lần pop phải ứng với một lần push trước đó. Chỉ cần chặn tổng số lần đẩy là chặn được độ phức tạp, kể cả khi có vòng while bên trong.

⚠️ Lỗi thường gặp

• Nhầm chiều heap. priority_queue<T> của C++ là max-heap; muốn min-heap phải viết priority_queue<T, vector<T>, greater<T>>. heapq của Python ngược lại, là min-heap. Dạng 1 cần min-heap (bỏ việc rẻ nhất), Moore-Hodgson cần max-heap (bỏ việc dài nhất). Triệu chứng: đáp án sai hoàn toàn ngay ở ví dụ mẫu. Luôn chạy tay ví dụ nhỏ để kiểm tra top().
• Viết comparator tùy biến bị ngược nghĩa. Comparator của priority_queue trả về true khi phần tử thứ nhất có độ ưu tiên thấp hơn (nằm dưới đáy). Muốn min-heap theo trường end thì viết return x.end > y.end; (dấu lớn hơn). Cách an toàn: đặt khóa so sánh ở đầu pair/tuple rồi dùng greater<>.
• Quét sai chiều hoặc sai khóa sắp xếp. Lập lịch phải quét theo hạn chót, không phải theo lợi nhuận; ghép đoạn với điểm phải chọn đoạn có đầu phải nhỏ nhất, không phải đầu trái nhỏ nhất. Sai khóa thì lập luận trao đổi không còn đúng. Triệu chứng: đúng ví dụ, sai test ẩn.
• Sai < và <= ở điều kiện dùng lại. Bài phòng khách sạn "rời đi thực sự sớm hơn" cần busy.top().first < a[i]; nếu đề cho phép rời và đến cùng ngày thì là <=. Tương tự, tham lam cổ phiếu dùng top < p: dùng <= không làm sai đáp số, chỉ sinh thêm các giao dịch lời bằng $0$ vô ích.
• Tràn số. Chi phí Huffman có thể tới $N·\sum a_i$; tổng thời gian trong Moore-Hodgson với $t_i,d_i$ tới ${10}^{18}$ có thể tới vài lần ${10}^{18}$, vẫn vừa long long nhưng không vừa nếu cộng thêm bừa. Dùng long long cho cả kiểu phần tử trong heap, không chỉ biến tổng.
• Gọi top()/pop() trên heap rỗng. Hành vi không xác định trong C++, IndexError trong Python. Luôn kiểm tra !pq.empty() trước, nhất là ở phần tử đầu tiên của tham lam hối hận và ở vòng prune.
• Xóa lười đếm sai kích thước. Sau khi đánh dấu xóa, pq.size() vẫn tính cả phần tử đã chết. Cân bằng hai heap theo size() thay vì bộ đếm phần tử hợp lệ sẽ làm trung vị lệch. Và phải prune trước khi đọc top(), nếu không có thể trả về phần tử đã bị xóa.
• Sinh trùng trạng thái khi duyệt $k$ nhỏ nhất. Từ $(i,j)$ đẩy cả $(i+1,j)$ và $(i,j+1)$ thì ô $(1,1)$ được sinh hai lần, kết quả bị lặp. Dùng cách "mỗi ô có đúng một cha" như trên, hoặc giữ tập visited. Đừng đẩy cả $N·M$ trạng thái vào heap ngay từ đầu: tốn bộ nhớ và mất ý nghĩa của heap.
• Tuple trong heapq so sánh cả phần tử thứ hai. Nếu hai phần tử có khóa bằng nhau, Python so sánh sang phần tử tiếp theo của tuple; nếu đó là object không so sánh được sẽ lỗi TypeError. Thêm một chỉ số tăng dần làm phần tử thứ hai để phá hòa.
• Nghĩ rằng tham lam hối hận được bán "hai lần một ngày". Việc đẩy $p$ hai lần không có nghĩa là ngày $p$ vừa bán vừa mua; hai bản sao cùng giá trị nên bản nào bị dùng trước cũng được hiểu là hoàn tác. Nếu đề cho phép nhiều cổ phiếu mỗi ngày hoặc có phí giao dịch thì phải dựng lại vé hoàn tác cho đúng, không chép máy móc.

Biến thể / Mở rộng

• Tham lam hối hận tổng quát: chọn đúng $k$ phần tử không kề nhau có tổng lớn nhất (lấy phần tử lớn nhất, thay nó bằng "vé" $a_{i-1}+a_{i+1}-a_i$ và gộp ba vị trí lại bằng danh sách liên kết), hay các bài ghép cặp có thể đổi ý. Tư tưởng đầy đủ hơn nằm ở Slope Trick.
• Kiểm tra khả thi trong tìm kiếm nhị phân: rất nhiều bài "cực tiểu hóa giá trị lớn nhất" chặt nhị phân đáp số rồi dùng một lượt quét với heap để kiểm tra, như ghép đoạn với điểm ở Dạng 4. Xem Sắp xếp và tìm kiếm.
• Ghép đoạn với điểm và cặp ghép: Dạng 4 là trường hợp đặc biệt của cặp ghép cực đại trên đồ thị hai phía; nhờ cấu trúc khoảng mà tham lam $O(N\log N)$ thay được thuật toán tổng quát.
• Hàng đợi hai đầu đơn điệu: khi các ứng viên hết hạn theo đúng thứ tự vào (cửa sổ trượt) và chỉ cần max/min, monotonic deque cho $O(N)$ thay vì $O(N\log N)$ của heap có xóa lười.
• Heap có thể gộp (leftist, skew heap, gộp nhỏ vào lớn): khi tham lam chạy trên cây và phải hợp nhất heap của các cây con.

Bài tập luyện

Luyện kỹ thuật

• Pha Chế Nguyên Liệu (mergefruit) (Trung cấp) gộp đống chi phí bằng tổng khối lượng: cài đặt trực tiếp Dạng 3, chú ý long long.
• Bố trí Phòng Khách sạn (roomalloc) (Nâng cao) số phòng tối thiểu và gán phòng cho từng khách: heap {ngày rời, số phòng} như Dạng 4, với điều kiện "rời thực sự sớm hơn" nên so sánh <.
• Lập lịch khởi hành (planning) (Nâng cao) quét các phút $k+1..k+n$, mỗi phút mở thêm các chuyến đã tới giờ gốc vào max-heap theo chi phí hoãn, rồi cho chuyến đắt nhất bay trước: đúng khuôn "mỗi ô lấp bằng ứng viên tốt nhất đã mở".
• Trung Vị Cửa Sổ Trượt (swmedian) (Nâng cao) hai heap giữ trung vị kết hợp xóa lười; cẩn thận quy ước lấy trung vị nhỏ hơn khi $k$ chẵn.
• Hoàn Thành Công Việc (jobcomp) (Nâng cao) mỗi việc có hạn bắt đầu $s_i$ nên hạn hoàn thành là $s_i+t_i$; đếm số việc nhiều nhất bằng Moore-Hodgson (max-heap độ dài), giá trị tới ${10}^{18}$ nên tính tổng cẩn thận.

Muốn luyện thêm tham lam hối hận: Phiếu Giảm Giá Bò (cowcoup) (Kỳ cựu) dùng phiếu cho $K$ con có giá dùng phiếu $C_i$ nhỏ nhất, rồi với mỗi con tiếp theo so sánh giá gốc $P_i$ với "giá phiếu $C_i$ + tiền phải trả thêm khi rút phiếu từ một con đã dùng" bằng ba heap.

Đề VOI

• Điều động (voi12_move) (Nâng cao) VOI 2012: chặt nhị phân theo thời điểm hoàn thành; với một thời điểm cố định, mỗi cảnh sát ứng với một đoạn cột tới được, và câu hỏi khả thi chính là bài ghép đoạn với điểm ở Dạng 4.
• Dòng xe vào bến (voi18_queue) (Nâng cao) VOI 2018: tính đơn điệu theo số xe đầu tiên cho phép chặt nhị phân; mỗi lần kiểm tra là một lượt quét các điểm đỗ với min-heap theo đầu phải. Để ý vì sao xếp xe ngay khi nó đến là sai.
• Chia phần (voi15_divide) (Nâng cao) VOI 2015: sau khi sắp các đồng tiền theo định giá của Vinh, hãy tự tìm điều kiện để một tập là phần hợp lệ của Sơn; điều kiện đó biến bài thành việc lấp dần các "ô", mỗi ô chọn ứng viên tốt nhất đã mở bằng max-heap, giống bài planning.
• Dãy xấp xỉ tăng (voi18_seq) (Kỳ cựu) VOI 2018: trước hết cần một phép biến đổi đưa điều kiện tăng ngặt về một dạng quen thuộc hơn; sau đó bài thuộc Slope Trick, với cơ chế max-heap "lấy đỉnh ra để sửa quyết định cũ" giống tham lam hối hận ở Dạng 2. Kỹ thuật heap chỉ là một phần lời giải: đề còn yêu cầu in dãy, nên cần thêm một bước khôi phục.