Lò sấy lúa (Đề tự luyện HSG Tin 12 – Bài 2)

Nguồn: Đề tự luyện HSG Tin học 12 – Bài 2 (đề tự soạn)Độ khó: Trung bìnhHàng đợi ưu tiênMô phỏng sự kiệnSắp xếp

Đề bài

Lò sấy lúa. Có $K$ lò sấy giống nhau và $N$ ghe lúa; ghe thứ $i$ tới ở phút $t_i$, cần sấy liên tục $d_i$ phút ở một lò. Bất cứ lúc nào có lò trống và có ghe đã tới mà chưa sấy, thầy Sơn cho ngay ghe cần ít thời gian sấy nhất vào lò (bằng nhau thì ghe tới sớm hơn, rồi số thứ tự nhỏ hơn). Lò xong ở phút $x$ thì trống ngay tại phút $x$, các ghe tới đúng phút $x$ được xét cùng các ghe đang chờ. Tính tổng thời gian chờ $\sum (s_i - t_i)$ ($s_i$ là phút bắt đầu sấy) và thời điểm ghe cuối cùng sấy xong.

Dữ liệu vào: dòng đầu $N, K$ ($1 \le N, K \le 2 \cdot 10^5$); $N$ dòng sau mỗi dòng $t_i, d_i$ ($0 \le t_i \le 10^9$, $1 \le d_i \le 10^6$), không nhất thiết theo thứ tự thời gian.

Kết quả: dòng 1 là tổng thời gian chờ, dòng 2 là thời điểm ghe cuối cùng sấy xong.

• Subtask 1 (30%): $N, K \le 2000$.
• Subtask 2 (30%): $K \le 10$.
• Subtask 3 (40%): không có ràng buộc gì thêm.

Input

7 2
7 4
7 5
8 4
11 7
0 2
0 3
6 3

Output

7
20

Giải thích

Phút bắt đầu sấy của ghe 1..7 lần lượt là 7, 11, 9, 13, 0, 0, 6. Ghe 2 chờ 4 phút (7 → 11), ghe 3 chờ 1 phút (8 → 9), ghe 4 chờ 2 phút (11 → 13), các ghe khác không phải chờ: tổng 7. Ghe 4 sấy xong cuối cùng, ở phút 13 + 7 = 20.

Dành cho học viênNộp bài trên ClueOJ

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Bộ test có chia subtask và có cả những test "bẫy", nên code đúng ý tưởng nhưng sai chi tiết nhỏ cũng sẽ bị trừ điểm đó.

Nộp bài Lò sấy lúa

Lời mở đầu

Đề đã nói rõ phải làm gì, không cần nghĩ ra chiến lược nào cả – đây là bài mô phỏng. Cái khó là mô phỏng sao cho đúng (thứ tự xử lý các việc xảy ra cùng một phút) và nhanh (thời gian lên tới hàng trăm tỉ phút, không thể đi từng phút).

Nhận xét 1 – chỉ cần dừng ở các "sự kiện". Tình hình ở bến chỉ thay đổi khi có ghe tới hoặc có lò sấy xong. Giữa hai sự kiện liên tiếp, không ai được xếp vào lò thêm. Vậy ta giữ biến now và mỗi lần nhảy thẳng tới sự kiện gần nhất: $\min(\text{phút ghe tiếp theo tới},\ \text{phút lò sớm xong nhất})$. Có tối đa $2N$ sự kiện.

Hình 1. Các thời điểm sự kiện của ví dụ. Ở phút 11 có hai sự kiện cùng lúc.

Nhận xét 2 – tại mỗi thời điểm, làm đúng thứ tự:

1. trả lại mọi lò sấy xong ở phút $\le$ now;
2. cho mọi ghe tới ở phút $\le$ now vào hàng chờ;
3. còn lò trống và còn ghe chờ thì lấy ghe có $d$ nhỏ nhất ra sấy, cộng thời gian chờ now $- t$.

Nếu đảo bước 2 và bước 3 (lò vừa xong là xếp ngay ghe đang chờ), một ghe tới đúng phút đó với $d$ nhỏ hơn sẽ bị "cướp lượt" – sai đề. Ví dụ của đề có một lúc như vậy (phút 11) nhưng ghe 4 tới lúc đó lại sấy lâu hơn ghe 2 đang chờ, nên làm sai thứ tự vẫn ra đúng 7 và 20. Đừng tin ví dụ!

Nhận xét 3 – các lò giống hệt nhau. Ta không cần biết ghe nào ở lò số mấy, chỉ cần biết có bao nhiêu lò trống và các lò đang bận sẽ xong ở phút nào.

Tràn số. Thời gian tới $10^9$, cộng thêm thời gian sấy chờ nối đuôi $2 \cdot 10^5 \cdot 10^6 = 2 \cdot 10^{11}$ phút; tổng thời gian chờ có thể tới cỡ $10^{16}$. Mọi biến thời gian phải là long long.

Ba cách dưới đây đều mô phỏng theo sự kiện như trên, chỉ khác cấu trúc dữ liệu để tìm "ghe có $d$ nhỏ nhất" và "lò sớm xong nhất".

Cách 1Mô phỏng, duyệt mảng · 30%Cách 2Hàng chờ dùng heap · 60%Cách 3Hai hàng đợi ưu tiên · 100%

Cách 1Mô phỏng, duyệt mảng – O(N·(N + K)) · 30%

Lưu fin[j] = phút lò $j$ rảnh, và đánh dấu ghe nào đã được xếp. Tại mỗi thời điểm now: tìm một lò có fin[j] ≤ now, duyệt mọi ghe đã tới mà chưa xếp để chọn ghe có $d$ nhỏ nhất, lặp đến khi hết lò trống hoặc hết ghe chờ. Sau đó duyệt lại để tìm sự kiện tiếp theo. Mỗi sự kiện tốn $O(N + K)$, có $O(N)$ sự kiện nên tổng $O(N \cdot (N + K))$ – khoảng $8 \cdot 10^6$ phép tính khi $N, K \le 2000$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<ll> t(n), d(n), fin(k, 0);        // fin[j]: lo j ranh tu thoi diem fin[j]
    for (int i = 0; i < n; i++) cin >> t[i] >> d[i];
    vector<bool> xep(n, false);              // ghe i da duoc xep lo chua
    int con = n;
    ll now = 0, tong = 0, xong = 0;
    while (con > 0) {
        while (true) {                       // con lo trong va con ghe dang cho thi xep
            int j = -1, b = -1;
            for (int x = 0; x < k; x++) if (fin[x] <= now) { j = x; break; }
            if (j < 0) break;
            for (int i = 0; i < n; i++)
                if (!xep[i] && t[i] <= now)
                    if (b < 0 || d[i] < d[b] || (d[i] == d[b] && t[i] < t[b])) b = i;
            if (b < 0) break;
            xep[b] = true; con--;
            tong += now - t[b];
            fin[j] = now + d[b];
            xong = max(xong, fin[j]);
        }
        ll nxt = LLONG_MAX;                  // su kien tiep theo: ghe toi hoac lo xong
        for (int i = 0; i < n; i++) if (!xep[i] && t[i] > now) nxt = min(nxt, t[i]);
        for (int x = 0; x < k; x++) if (fin[x] > now) nxt = min(nxt, fin[x]);
        now = nxt;
    }
    cout << tong << "\n" << xong << "\n";
    return 0;
}

import sys


def main():
    data = sys.stdin.buffer.read().split()
    n, k = int(data[0]), int(data[1])
    t = list(map(int, data[2:2 + 2 * n:2]))
    d = list(map(int, data[3:3 + 2 * n:2]))
    fin = [0] * k              # lo j ranh tu thoi diem fin[j]
    xep = [False] * n          # ghe i da duoc xep lo chua
    con = n
    now = tong = xong = 0
    INF = 1 << 62
    while con > 0:
        while True:            # con lo trong va con ghe dang cho thi xep
            j = -1
            for x in range(k):
                if fin[x] <= now:
                    j = x
                    break
            if j < 0:
                break
            b = -1
            for i in range(n):
                if not xep[i] and t[i] <= now:
                    if b < 0 or d[i] < d[b] or (d[i] == d[b] and t[i] < t[b]):
                        b = i
            if b < 0:
                break
            xep[b] = True
            con -= 1
            tong += now - t[b]
            fin[j] = now + d[b]
            xong = max(xong, fin[j])
        nxt = INF              # su kien tiep theo: ghe toi hoac lo xong
        for i in range(n):
            if not xep[i] and now < t[i] < nxt:
                nxt = t[i]
        for x in range(k):
            if now < fin[x] < nxt:
                nxt = fin[x]
        now = nxt
    sys.stdout.write("%d\n%d\n" % (tong, xong))


main()

Không gian$O(N + K)$

Thời gian$O(N \cdot (N + K))$

Cách 2Hàng chờ dùng hàng đợi ưu tiên – O(N log N + N·K) · 60%

Chỗ tốn nhất của Cách 1 là tìm ghe có $d$ nhỏ nhất trong hàng chờ – hàng chờ có thể dài cả trăm nghìn ghe. Đây đúng là việc của hàng đợi ưu tiên (priority_queue, heap): thêm một ghe hoặc lấy ra ghe nhỏ nhất đều mất $O(\log N)$. Ta lưu mỗi ghe là bộ (d, t, i) – so sánh bộ theo thứ tự từ điển chính là luật ưu tiên của đề – và dùng greater để lấy phần tử nhỏ nhất.

Để ghe được thêm vào hàng chờ đúng lúc tới, ta sắp xếp các ghe theo $t$ rồi dùng con trỏ p chỉ ghe tiếp theo sẽ tới. Phần lò vẫn duyệt mảng fin nên mỗi sự kiện tốn $O(K)$: với $K \le 10$ thì quá nhanh, nhưng với $K = 10^5$ thì không kịp.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, int> Ghe;          // (thoi gian say, thoi diem toi, so thu tu)
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<ll> t(n), d(n), fin(k, 0);        // fin[j]: lo j ranh tu thoi diem fin[j]
    for (int i = 0; i < n; i++) cin >> t[i] >> d[i];
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int a, int b) { return t[a] < t[b]; });
    priority_queue<Ghe, vector<Ghe>, greater<Ghe>> cho;
    int p = 0;
    ll now = 0, tong = 0, xong = 0;
    while (p < n || !cho.empty()) {
        while (p < n && t[id[p]] <= now) { cho.push({d[id[p]], t[id[p]], id[p]}); p++; }
        for (int x = 0; x < k && !cho.empty(); x++)       // duyet tung lo
            if (fin[x] <= now) {
                auto [dd, tt, i] = cho.top(); cho.pop();
                tong += now - tt;
                fin[x] = now + dd;
                xong = max(xong, fin[x]);
            }
        ll nxt = LLONG_MAX;
        if (p < n) nxt = t[id[p]];
        for (int x = 0; x < k; x++) if (fin[x] > now) nxt = min(nxt, fin[x]);
        now = nxt;
    }
    cout << tong << "\n" << xong << "\n";
    return 0;
}

import sys
from heapq import heappush, heappop


def main():
    data = sys.stdin.buffer.read().split()
    n, k = int(data[0]), int(data[1])
    t = list(map(int, data[2:2 + 2 * n:2]))
    d = list(map(int, data[3:3 + 2 * n:2]))
    fin = [0] * k              # lo j ranh tu thoi diem fin[j]
    order = sorted(range(n), key=t.__getitem__)
    cho = []
    p = 0
    now = tong = xong = 0
    INF = 1 << 62
    while p < n or cho:
        while p < n and t[order[p]] <= now:
            i = order[p]; p += 1
            heappush(cho, (d[i], t[i], i))
        for x in range(k):     # duyet tung lo
            if not cho:
                break
            if fin[x] <= now:
                dd, tt, i = heappop(cho)
                tong += now - tt
                fin[x] = now + dd
                if fin[x] > xong:
                    xong = fin[x]
        nxt = t[order[p]] if p < n else INF
        for x in range(k):
            if now < fin[x] < nxt:
                nxt = fin[x]
        now = nxt
    sys.stdout.write("%d\n%d\n" % (tong, xong))


main()

Không gian$O(N + K)$

Thời gian$O(N \log N + N \cdot K)$

Cách 3Hai hàng đợi ưu tiên – O(N log N) · 100%

Theo nhận xét 3, phần lò chỉ cần: biến trong = số lò đang trống, và một hàng đợi ưu tiên lo chứa phút xong của các lò đang bận (lấy ra phút nhỏ nhất). Mỗi ghe được đẩy vào và lấy ra mỗi hàng đợi đúng một lần, nên cả bài chỉ còn $O(N \log N)$.

Các bạn nhập thử dữ liệu (tối đa 10 ghe) và bấm "Tiếp" để xem từng thời điểm sự kiện:

K Phút tới t Thời gian sấy d

Ví dụ nhanh:

Bẫy thường gặp

• Xếp ghe đang chờ vào lò vừa xong trước khi nhận các ghe tới cùng phút đó (ví dụ của đề không bắt được lỗi này).
• Sắp xếp mọi ghe theo $d$ ngay từ đầu rồi cho lần lượt vào lò rảnh sớm nhất: ghe chưa tới cũng được "ưu tiên" – sai, dù vẫn ra đúng ví dụ.
• Phục vụ theo thứ tự tới (ai tới trước sấy trước) – đọc sót luật ưu tiên.
• Dùng int cho thời gian hoặc tổng thời gian chờ.

Trong bản Python, mình gộp khóa $(d, t)$ thành một số nguyên $d \cdot 2^{30} + t$ (vì $t < 2^{30}$) để heap so sánh số thay vì so sánh bộ, chạy nhanh hơn khoảng 3 lần mà thứ tự ưu tiên không đổi.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef tuple<ll, ll, int> Ghe;          // (thoi gian say, thoi diem toi, so thu tu)
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<ll> t(n), d(n);
    for (int i = 0; i < n; i++) cin >> t[i] >> d[i];
    vector<int> id(n);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int a, int b) { return t[a] < t[b]; });
    priority_queue<Ghe, vector<Ghe>, greater<Ghe>> cho;   // ghe dang cho
    priority_queue<ll, vector<ll>, greater<ll>> lo;       // luc xong cua cac lo dang say
    int trong = k, p = 0;
    ll now = 0, tong = 0, xong = 0;
    while (p < n || !cho.empty()) {
        while (!lo.empty() && lo.top() <= now) { lo.pop(); trong++; }
        while (p < n && t[id[p]] <= now) { cho.push({d[id[p]], t[id[p]], id[p]}); p++; }
        while (trong > 0 && !cho.empty()) {
            auto [dd, tt, i] = cho.top(); cho.pop();
            tong += now - tt;
            lo.push(now + dd); trong--;
            xong = max(xong, now + dd);
        }
        ll nxt = LLONG_MAX;
        if (p < n) nxt = t[id[p]];
        if (!lo.empty()) nxt = min(nxt, lo.top());
        now = nxt;
    }
    cout << tong << "\n" << xong << "\n";
    return 0;
}

import sys
from heapq import heappush, heappop


def main():
    data = sys.stdin.buffer.read().split()
    n, k = int(data[0]), int(data[1])
    t = list(map(int, data[2:2 + 2 * n:2]))
    d = list(map(int, data[3:3 + 2 * n:2]))
    order = sorted(range(n), key=t.__getitem__)
    ts = [t[i] for i in order]
    ds = [d[i] for i in order]
    # ghe dang cho: khoa (d, t) gop thanh mot so nguyen d * 2^30 + t (t < 2^30) de heap chay nhanh
    cho = []
    lo = []         # luc xong cua cac lo dang say
    trong = k
    p = 0
    now = tong = xong = 0
    INF = 1 << 62
    MASK = (1 << 30) - 1
    while p < n or cho:
        while lo and lo[0] <= now:
            heappop(lo); trong += 1
        while p < n and ts[p] <= now:
            heappush(cho, (ds[p] << 30) | ts[p]); p += 1
        while trong > 0 and cho:
            key = heappop(cho)
            dd = key >> 30
            tong += now - (key & MASK)
            e = now + dd
            heappush(lo, e); trong -= 1
            if e > xong:
                xong = e
        nxt = ts[p] if p < n else INF
        if lo and lo[0] < nxt:
            nxt = lo[0]
        now = nxt
    sys.stdout.write("%d\n%d\n" % (tong, xong))


main()

Không gian$O(N)$

Thời gian$O(N \log N)$

C++▶ Chạy tay từng dòng codeTheo dõi hai hàng đợi ưu tiên cho và lo khi nhảy qua từng thời điểm sự kiện.

Dữ liệu vào (stdin) – sửa thoải mái7 2 7 4 7 5 8 4 11 7 0 2 0 3 6 3

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3typedef long long ll;

4typedef tuple<ll, ll, int> Ghe; // (thoi gian say, thoi diem toi, so thu tu)

5int main() {

6 ios::sync_with_stdio(false); cin.tie(nullptr);

7 int n, k;

8 cin >> n >> k;

9 vector<ll> t(n), d(n);

10 for (int i = 0; i < n; i++) cin >> t[i] >> d[i];

11 vector<int> id(n);

12 iota(id.begin(), id.end(), 0);

13 sort(id.begin(), id.end(), [&](int a, int b) { return t[a] < t[b]; });

14 priority_queue<Ghe, vector<Ghe>, greater<Ghe>> cho; // ghe dang cho

15 priority_queue<ll, vector<ll>, greater<ll>> lo; // luc xong cua cac lo dang say

16 int trong = k, p = 0;

17 ll now = 0, tong = 0, xong = 0;

18 while (p < n || !cho.empty()) {

19 while (!lo.empty() && lo.top() <= now) { lo.pop(); trong++; }

20 while (p < n && t[id[p]] <= now) { cho.push({d[id[p]], t[id[p]], id[p]}); p++; }

21 while (trong > 0 && !cho.empty()) {

22 auto [dd, tt, i] = cho.top(); cho.pop();

23 tong += now - tt;

24 lo.push(now + dd); trong--;

25 xong = max(xong, now + dd);

26 }

27 ll nxt = LLONG_MAX;

28 if (p < n) nxt = t[id[p]];

29 if (!lo.empty()) nxt = min(nxt, lo.top());

30 now = nxt;

31 }

32 cout << tong << "\n" << xong << "\n";

33 return 0;

34}

ChậmVừaNhanhRất nhanh

Bộ test chấm "bắt" những lỗi nào?

Bộ test có 34 test: 13 test subtask 1 ($N, K \le 2000$), 10 test subtask 2 ($N \approx 2 \cdot 10^5$, $K \le 10$, hàng chờ rất dài), 11 test subtask 3 ($N \approx 2 \cdot 10^5$, $K$ từ $3 \cdot 10^4$ đến $1{,}9 \cdot 10^5$). Nhiều test có $t_i, d_i$ là bội của 10, 100 hoặc 1000 để có thật nhiều lúc "lò xong đúng lúc ghe tới"; có test mọi ghe tới phút 0, test ghe tới sát phút $10^9$, test chỉ có hai loại thời gian sấy rất ngắn và rất dài.

Cách làm	Sub 1 (30%)	Sub 2 (30%)	Sub 3 (40%)	Điểm
Cách 1 – mô phỏng, duyệt mảng ghe và lò	Đúng	TLE	TLE	30
Cách 2 – hàng chờ dùng heap, duyệt mảng lò	Đúng	Đúng	TLE	60
Cách 3 – hai hàng đợi ưu tiên	Đúng	Đúng	Đúng	100
Sai 1 – lò vừa xong là xếp ngay, chưa nhận ghe tới cùng phút	5/13 test	2/10 test	3/11 test	≈ 28
Sai 2 – ai tới trước sấy trước	1/13 test	WA	WA	≈ 2
Sai 3 – dùng int	9/13 test	WA	1/11 test	≈ 24
Sai 4 – sắp xếp mọi ghe theo d rồi xếp lần lượt	4/13 test	1/10 test	2/11 test	≈ 19

Ghi chú của mình: các cách C++ ở trên đã được chấm thử với đúng bộ test của bài: Cách 1 đúng 13/13 test subtask 1 và chạy quá 3 giây ở mọi test còn lại (đo riêng hơn 30 giây); Cách 2 đúng hết subtask 1, 2 và quá 3 giây ở mọi test subtask 3 (đo riêng từ 6 đến hơn 30 giây); Cách 3 đúng 34/34 test, test lâu nhất khoảng 0,3 giây. Lỗi "xếp ngay khi lò vừa xong" chỉ ăn may ở các test gần như không có lúc nào lò xong đúng phút có ghe tới (ví dụ: mọi ghe tới phút 0); lỗi int chỉ qua các test nhỏ của subtask 1.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇