Mâm cỗ (Đề tự luyện HSG Tin quốc gia – Bài 4)

Nguồn: Đề tự luyện HSG Tin học quốc gia #05 – Bài 4 (đề tự soạn)Độ khó: KhóHàng đợi ưu tiênLiệt kê K phương án tốt nhấtCây sinh trạng tháiSắp xếp theo độ chênh

Đề bài

Mâm cỗ. Mỗi mâm gồm $N$ món; món $i$ có $m_i$ ghe bán với giá $c_{i,1}, \ldots, c_{i,m_i}$. Một mâm chọn cho mỗi món đúng một ghe, giá mâm là tổng. Hai mâm khác nhau nếu có ít nhất một món mua ở hai ghe khác nhau. Chọn $K$ mâm đôi một khác nhau với tổng tiền nhỏ nhất: in tổng tiền đó và giá của mâm đắt nhất trong $K$ mâm.

Dữ liệu vào: dòng 1: $N$, $K$; dòng $i + 1$: $m_i$ rồi $m_i$ giá. $1 \le N \le 2 \cdot 10^5$, $\sum m_i \le 2 \cdot 10^5$, $1 \le c \le 10^8$, $1 \le K \le 2 \cdot 10^5$, $K \le \prod m_i$.

Kết quả: dòng 1: tổng tiền nhỏ nhất; dòng 2: giá mâm đắt nhất.

• Subtask 1 (10%): $\prod m_i \le 2 \cdot 10^5$.
• Subtask 2 (15%): $N = 2$.
• Subtask 3 (20%): $N \le 2000$ và $K \le 2000$.
• Subtask 4 (25%): $m_i = 2$ với mọi $i$.
• Subtask 5 (30%): không có ràng buộc gì thêm.

Giới hạn thời gian: C++ 1 giây, Python/PyPy 3 giây.

Input

4 6
3 10 5 12
3 7 11 3
2 4 9
3 1 7 10

Output

105
20

Giải thích

Sáu mâm rẻ nhất: $13 = 5+3+4+1$, $17 = 5+7+4+1$, $18 = 10+3+4+1$, $18 = 5+3+9+1$, $19 = 5+3+4+7$, $20 = 12+3+4+1$. Tổng $105$, mâm đắt nhất $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 Mâm cỗ

Lời mở đầu

Đây là bài cuối của đề. Nhìn qua thì đơn giản: "tìm $K$ tổng nhỏ nhất". Nhưng số mâm có thể lên tới $2^{100000}$, nên không thể liệt kê hết. Và nhìn ví dụ, rất dễ "đoán" rằng $K$ mâm rẻ nhất chỉ khác mâm rẻ nhất ở một món — ví dụ cố tình cho cách đoán này ra đúng, nhưng với $K$ lớn thì sai bét (mâm đổi 2, 3, ... món cũng rất rẻ nếu các độ chênh nhỏ).

Kỹ thuật của bài là liệt kê $K$ phương án tốt nhất bằng hàng đợi ưu tiên (giống Dijkstra trên một "cây" các phương án): lấy ra phương án rẻ nhất chưa xét, rồi đẩy vào vài phương án "kế tiếp" của nó. Để đúng và nhanh, cây đó phải thỏa ba điều:

1. Không trùng: mỗi phương án có đúng một "cha" — để không bị đếm hai lần.
2. Con không rẻ hơn cha: để thứ tự lấy ra khỏi heap đúng là thứ tự tăng dần.
3. Ít con: mỗi phương án chỉ sinh $O(1)$ con — để tổng số thao tác là $O(K \log K)$.

Cả bài là hành trình đi từ cây "nhiều con" (Cách 3) tới cây "chỉ 3 con" (Cách 5).

Hình 1. Cây sinh 8 tập con của $\{d_0, d_1, d_2\}$: mỗi tập con xuất hiện đúng một lần, và vì $d$ đã sắp tăng nên tổng của con luôn $\ge$ tổng của cha. Đây là trái tim của Cách 4 và Cách 5.

Cách 1Liệt kê hết · 10%Cách 2Hai món: heap · 25%Cách 3Cây N con · 45%Cách 4Hai ghe: thêm/thay · 70%Cách 5Cây 3 con · 100%

Cách 1Liệt kê mọi mâm – O(P log P) · 10%

Khi tích $P = \prod m_i \le 2 \cdot 10^5$, ta ghép dần từng món: danh sách giá các "nửa mâm" nhân với từng ghe của món tiếp theo. Cuối cùng sắp xếp $P$ giá, cộng $K$ giá đầu.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n, K; scanf("%d %d", &n, &K);
    vector<ll> all = {0};                    // gia cua moi mam ghep tu cac mon da xet
    for (int i = 0; i < n; i++) {
        int m; scanf("%d", &m);
        vector<ll> c(m); for (auto& x : c) scanf("%lld", &x);
        vector<ll> nx; nx.reserve(all.size() * m);
        for (ll s : all) for (ll x : c) nx.push_back(s + x);
        all.swap(nx);
    }
    sort(all.begin(), all.end());
    ll tot = 0;
    for (int k = 0; k < K; k++) tot += all[k];
    printf("%lld\n%lld\n", tot, all[K - 1]);
}

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    pos = 2
    allv = [0]                               # gia cua moi mam ghep tu cac mon da xet
    for _ in range(n):
        m = int(data[pos]); pos += 1
        c = [int(x) for x in data[pos:pos + m]]; pos += m
        allv = [s + x for s in allv for x in c]
    allv.sort()
    print(sum(allv[:K]))
    print(allv[K - 1])

main()

Không gian$O(P)$

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

Cách 2Hai món: hàng đợi ưu tiên trên cặp (i, j) – O(K log K) · 25%

Với $N = 2$: sắp hai dãy giá $A$, $B$ tăng dần. Mâm $(i, j)$ có giá $A_i + B_j$. Mâm rẻ nhất là $(0, 0)$. Ta cần cho mỗi mâm $(i, j) \ne (0, 0)$ đúng một cha rẻ hơn hoặc bằng nó:

• nếu $j \ge 1$: cha là $(i, j - 1)$;
• nếu $j = 0$: cha là $(i - 1, 0)$.

Đảo ngược lại: từ $(i, j)$ sinh $(i, j + 1)$, và nếu $j = 0$ thì sinh thêm $(i + 1, 0)$. Mỗi lần lấy khỏi heap đẩy vào tối đa 2 phần tử, lấy đúng $K$ lần. Đây là bài "kinh điển" mà nhiều bạn đã gặp.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n, K; scanf("%d %d", &n, &K);
    vector<vector<ll>> c(n);
    for (int i = 0; i < n; i++) {
        int m; scanf("%d", &m); c[i].resize(m);
        for (auto& x : c[i]) scanf("%lld", &x);
    }
    if (n == 2) {                            // Cach 2: hai mon, hang doi uu tien tren cap (i, j)
        vector<ll>& A = c[0]; vector<ll>& B = c[1];
        sort(A.begin(), A.end()); sort(B.begin(), B.end());
        priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
        pq.push({A[0] + B[0], 0, 0});
        ll tot = 0, last = 0;
        for (int k = 0; k < K; k++) {
            auto [s, i, j] = pq.top(); pq.pop();
            tot += s; last = s;
            if (j + 1 < (int)B.size()) pq.push({A[i] + B[j + 1], i, j + 1});
            if (j == 0 && i + 1 < (int)A.size()) pq.push({A[i + 1] + B[0], i + 1, 0});
        }
        printf("%lld\n%lld\n", tot, last);
        return 0;
    }
    vector<ll> all = {0};                    // con lai: Cach 1 liet ke het
    for (int i = 0; i < n; i++) {
        vector<ll> nx; nx.reserve(all.size() * c[i].size());
        for (ll s : all) for (ll x : c[i]) nx.push_back(s + x);
        all.swap(nx);
    }
    sort(all.begin(), all.end());
    ll tot = 0;
    for (int k = 0; k < K; k++) tot += all[k];
    printf("%lld\n%lld\n", tot, all[K - 1]);
}

import sys
from heapq import heappush, heappop

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    pos = 2; c = []
    for _ in range(n):
        m = int(data[pos]); pos += 1
        c.append([int(x) for x in data[pos:pos + m]]); pos += m
    if n == 2:                               # Cach 2: hai mon, hang doi uu tien tren cap (i, j)
        A = sorted(c[0]); B = sorted(c[1])
        pq = [(A[0] + B[0], 0, 0)]
        tot = 0; last = 0
        for _ in range(K):
            s, i, j = heappop(pq)
            tot += s; last = s
            if j + 1 < len(B):
                heappush(pq, (A[i] + B[j + 1], i, j + 1))
            if j == 0 and i + 1 < len(A):
                heappush(pq, (A[i + 1] + B[0], i + 1, 0))
        print(tot); print(last)
        return
    allv = [0]                               # con lai: Cach 1 liet ke het
    for g in c:
        allv = [s + x for s in allv for x in g]
    allv.sort()
    print(sum(allv[:K])); print(allv[K - 1])

main()

Không gian$O(K)$

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

Cách 3Nhiều món: cây "đổi món cuối cùng" – O(K · N log) · 45%

Sắp giá mỗi món tăng dần, mâm rẻ nhất là $base = \sum c_{i,0}$. Món chỉ có 1 ghe thì bỏ qua (luôn chọn ghe đó). Một mâm được mô tả bởi dãy chỉ số $(j_0, j_1, \ldots)$. Chọn cha thế này:

Cha duy nhất

Gọi $i$ là món cuối cùng có $j_i \ge 1$. Cha của mâm là mâm giống hệt nhưng $j_i$ giảm đi 1. Cha rẻ hơn hoặc bằng con vì giá đã sắp tăng.

Đảo lại: từ trạng thái $(s, i, j)$ — "món cuối khác ghe rẻ nhất là $i$, đang ở ghe $j$, giá mâm $s$" — sinh ra $(i, j + 1)$ và $(t, 1)$ với mọi $t > i$. Đúng, nhưng mỗi trạng thái có tới $N$ con: tổng $O(K \cdot N)$ thao tác, chỉ đủ cho $N, K \le 2000$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n, K; scanf("%d %d", &n, &K);
    vector<vector<ll>> g; ll base = 0;
    for (int i = 0; i < n; i++) {
        int m; scanf("%d", &m); vector<ll> c(m);
        for (auto& x : c) scanf("%lld", &x);
        sort(c.begin(), c.end()); base += c[0];
        if (m >= 2) g.push_back(c);
    }
    int M = g.size();
    // trang thai (s, i, j): mon i la mon CUOI CUNG khong chon ghe re nhat, dang chon ghe j
    // con: (i, j + 1) va (t, 1) voi moi t > i  -> moi mam sinh ra dung mot lan
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
    for (int t = 0; t < M; t++) pq.push({base + g[t][1] - g[t][0], t, 1});
    ll tot = base, last = base;
    for (int k = 1; k < K; k++) {
        auto [s, i, j] = pq.top(); pq.pop();
        tot += s; last = s;
        if (j + 1 < (int)g[i].size()) pq.push({s - g[i][j] + g[i][j + 1], i, j + 1});
        for (int t = i + 1; t < M; t++) pq.push({s + g[t][1] - g[t][0], t, 1});
    }
    printf("%lld\n%lld\n", tot, last);
}

import sys
from heapq import heappush, heappop

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    pos = 2; base = 0; g = []
    for _ in range(n):
        m = int(data[pos]); pos += 1
        c = sorted(map(int, data[pos:pos + m])); pos += m
        base += c[0]
        if m >= 2:
            g.append(c)
    M = len(g)
    d = [c[1] - c[0] for c in g]
    # trang thai (s, i, j): mon i la mon cuoi cung khong chon ghe re nhat, dang chon ghe j
    pq = [(base + d[t], t, 1) for t in range(M)]
    pq.sort()
    tot = base; last = base
    for _ in range(K - 1):
        s, i, j = heappop(pq)
        tot += s; last = s
        c = g[i]
        if j + 1 < len(c):
            heappush(pq, (s - c[j] + c[j + 1], i, j + 1))
        for t in range(i + 1, M):
            heappush(pq, (s + d[t], t, 1))
    print(tot); print(last)

main()

Không gian$O(K \cdot N)$

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

Cách 4Mỗi món 2 ghe: chọn tập con các độ chênh, "thêm hoặc thay" – O(K log K) · 70%

Khi mọi món có đúng 2 ghe, mâm = $base$ + tổng một tập con các độ chênh $d_i = c_{i,1} - c_{i,0} \ge 0$. Bài trở thành: tìm $K$ tổng tập con nhỏ nhất. Mẹo then chốt:

Sắp $d$ tăng dần, mỗi tập con chỉ sinh 2 con

Xét tập con có phần tử lớn nhất (theo chỉ số) là $d_i$. Từ nó sinh: "thêm" $d_{i+1}$ (tổng $s + d_{i+1}$) và "thay" $d_i$ bằng $d_{i+1}$ (tổng $s - d_i + d_{i+1}$). Vì $d_{i+1} \ge d_i \ge 0$ nên cả hai con đều không rẻ hơn cha.

Vì sao mỗi tập con xuất hiện đúng một lần? Với tập con có phần tử lớn nhất $d_i$ ($i \ge 1$): nếu nó chứa $d_{i-1}$ thì cha là tập bỏ $d_i$ (đã "thêm"); nếu không chứa $d_{i-1}$ thì cha là tập thay $d_i$ bằng $d_{i-1}$ (đã "thay"). Tập $\{d_0\}$ là gốc. Xem Hình 1. Nếu quên sắp $d$, phép "thay" có thể làm tổng giảm — con rẻ hơn cha — và thứ tự lấy ra khỏi heap sai.

Các độ chênh d K

Ví dụ nhanh:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n, K; scanf("%d %d", &n, &K);
    vector<vector<ll>> g; ll base = 0; bool two = true;
    for (int i = 0; i < n; i++) {
        int m; scanf("%d", &m); vector<ll> c(m);
        for (auto& x : c) scanf("%lld", &x);
        sort(c.begin(), c.end()); base += c[0];
        if (m >= 2) g.push_back(c);
        if (m > 2) two = false;
    }
    int M = g.size();
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
    ll tot = base, last = base;
    if (two) {
        // Cach 4: moi mon chi co 2 ghe -> chon mot tap con cac "do chenh" d
        vector<ll> d(M);
        for (int t = 0; t < M; t++) d[t] = g[t][1] - g[t][0];
        sort(d.begin(), d.end());
        // trang thai (s, i): d[i] la phan tu lon nhat duoc chon
        if (M > 0) pq.push({base + d[0], 0, 0});
        for (int k = 1; k < K; k++) {
            auto [s, i, z] = pq.top(); pq.pop();
            tot += s; last = s;
            if (i + 1 < M) {
                pq.push({s + d[i + 1], i + 1, 0});          // chon them d[i+1]
                pq.push({s - d[i] + d[i + 1], i + 1, 0});   // doi d[i] thanh d[i+1]
            }
        }
    } else {                                 // con lai: Cach 3
        for (int t = 0; t < M; t++) pq.push({base + g[t][1] - g[t][0], t, 1});
        for (int k = 1; k < K; k++) {
            auto [s, i, j] = pq.top(); pq.pop();
            tot += s; last = s;
            if (j + 1 < (int)g[i].size()) pq.push({s - g[i][j] + g[i][j + 1], i, j + 1});
            for (int t = i + 1; t < M; t++) pq.push({s + g[t][1] - g[t][0], t, 1});
        }
    }
    printf("%lld\n%lld\n", tot, last);
}

import sys
from heapq import heappush, heappop

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    pos = 2; base = 0; g = []; two = True
    for _ in range(n):
        m = int(data[pos]); pos += 1
        c = sorted(map(int, data[pos:pos + m])); pos += m
        base += c[0]
        if m >= 2:
            g.append(c)
        if m > 2:
            two = False
    M = len(g)
    tot = base; last = base
    if two:
        # Cach 4: moi mon chi co 2 ghe -> chon mot tap con cac do chenh d
        d = sorted(c[1] - c[0] for c in g)
        pq = [(base + d[0], 0)] if M > 0 else []
        for _ in range(K - 1):
            s, i = heappop(pq)
            tot += s; last = s
            if i + 1 < M:
                heappush(pq, (s + d[i + 1], i + 1))          # chon them d[i+1]
                heappush(pq, (s - d[i] + d[i + 1], i + 1))   # doi d[i] thanh d[i+1]
    else:                                    # con lai: Cach 3
        d = [c[1] - c[0] for c in g]
        pq = [(base + d[t], t, 1) for t in range(M)]
        pq.sort()
        for _ in range(K - 1):
            s, i, j = heappop(pq)
            tot += s; last = s
            c = g[i]
            if j + 1 < len(c):
                heappush(pq, (s - c[j] + c[j + 1], i, j + 1))
            for t in range(i + 1, M):
                heappush(pq, (s + d[t], t, 1))
    print(tot); print(last)

main()

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

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

Cách 5Ghép hai ý: cây 3 con – O((Σm + K) log) · 100%

Giờ mỗi món có nhiều ghe. Bỏ các món 1 ghe, sắp các món còn lại theo $d_i = c_{i,1} - c_{i,0}$ tăng dần. Trạng thái $(s, i, j)$: món $i$ là món cuối cùng không chọn ghe rẻ nhất, nó đang chọn ghe $j \ge 1$; mọi món sau $i$ chọn ghe rẻ nhất. Từ đó sinh tối đa 3 con:

1. Lên ghe kế tiếp trong cùng món: $(i, j + 1)$, giá $s - c_{i,j} + c_{i,j+1}$.
2. Thêm món $i + 1$ (giữ nguyên món $i$): $(i + 1, 1)$, giá $s + d_{i+1}$.
3. Thay — chỉ khi $j = 1$: trả món $i$ về ghe rẻ nhất, món $i + 1$ lên ghe thứ hai: $(i + 1, 1)$, giá $s - d_i + d_{i+1}$.

Điều kiện j = 1 ở con thứ 3 là bắt buộc!

Nếu món $i$ đang ở ghe $j \ge 2$ mà vẫn "thay", ta tạo ra một mâm "ma" có giá $s - d_i + d_{i+1}$ không ứng với mâm thật nào (trả món $i$ về ghe rẻ nhất phải trừ $c_{i,j} - c_{i,0}$ chứ không phải $d_i$), hoặc sinh trùng mâm. Mâm với món $i$ ở ghe rẻ nhất và món $i+1$ ở ghe thứ hai đã được sinh từ trạng thái $(i, 1)$ rồi. Lỗi này không bao giờ lộ ra khi mọi món chỉ có 2 ghe (vì luôn $j = 1$) — bảng chấm cuối bài cho thấy nó vẫn ăn trọn subtask 4.

Cha duy nhất: với trạng thái $(i, j)$, $j \ge 2$ thì cha là $(i, j - 1)$; $j = 1$ thì: nếu món $i - 1$ đang khác ghe rẻ nhất, cha là mâm bỏ món $i$ về ghe rẻ nhất (con loại 2); nếu không, cha là mâm có món $i - 1$ ở ghe thứ hai thay cho món $i$ (con loại 3). Con luôn không rẻ hơn cha nhờ giá đã sắp và $d$ đã sắp. Mỗi lần lấy ra đẩy vào $\le 3$ phần tử, lấy $K - 1$ lần.

Các món (giá cách nhau bởi dấu cách, món cách nhau bởi |) K

Ví dụ nhanh:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct St { ll s; int i, j; };
struct Cmp { bool operator()(const St& x, const St& y) const { return x.s > y.s; } };
int main() {
    int n, K;
    scanf("%d %d", &n, &K);
    vector<vector<ll>> g;                  // cac mon co tu 2 ghe tro len
    ll base = 0;                           // mam re nhat: mon nao cung chon ghe re nhat
    for (int i = 0; i < n; i++) {
        int m; scanf("%d", &m);
        vector<ll> c(m);
        for (auto& x : c) scanf("%lld", &x);
        sort(c.begin(), c.end());
        base += c[0];
        if (m >= 2) g.push_back(c);
    }
    // sap cac mon theo do chenh d = c[1] - c[0] tang dan
    sort(g.begin(), g.end(), [](const vector<ll>& x, const vector<ll>& y) { return x[1] - x[0] < y[1] - y[0]; });
    int M = g.size();
    auto d = [&](int i) { return g[i][1] - g[i][0]; };
    // trang thai (s, i, j): mon i dang chon ghe j >= 1, cac mon sau i chon ghe re nhat
    priority_queue<St, vector<St>, Cmp> pq;
    ll total = base, last = base;
    if (M > 0) pq.push({base + d(0), 0, 1});
    for (int cnt = 1; cnt < K; cnt++) {
        St t = pq.top(); pq.pop();
        total += t.s; last = t.s;
        int i = t.i, j = t.j;
        if (j + 1 < (int)g[i].size()) pq.push({t.s - g[i][j] + g[i][j + 1], i, j + 1});   // mon i doi sang ghe dat hon ke tiep
        if (i + 1 < M) {
            pq.push({t.s + d(i + 1), i + 1, 1});                     // giu mon i, mon i+1 doi sang ghe thu hai
            if (j == 1) pq.push({t.s - d(i) + d(i + 1), i + 1, 1});  // tra mon i ve ghe re nhat
        }
    }
    printf("%lld\n%lld\n", total, last);
}

import sys
from heapq import heappush, heappop

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); K = int(data[1])
    pos = 2
    base = 0
    grp = []                                   # cac mon co tu 2 ghe tro len (da sap xep)
    for _ in range(n):
        m = int(data[pos]); pos += 1
        c = sorted(map(int, data[pos:pos + m])); pos += m
        base += c[0]
        if m >= 2:
            grp.append(c)
    grp.sort(key=lambda c: c[1] - c[0])        # theo do chenh d = c[1] - c[0] tang dan
    M = len(grp)
    d = [c[1] - c[0] for c in grp]
    total = base; last = base
    pq = []
    if M > 0:
        pq.append((base + d[0], 0, 1))
    for _ in range(K - 1):
        s, i, j = heappop(pq)
        total += s; last = s
        c = grp[i]
        if j + 1 < len(c):
            heappush(pq, (s - c[j] + c[j + 1], i, j + 1))      # mon i doi sang ghe ke tiep
        if i + 1 < M:
            dn = d[i + 1]
            heappush(pq, (s + dn, i + 1, 1))                   # giu mon i, doi mon i+1
            if j == 1:
                heappush(pq, (s - d[i] + dn, i + 1, 1))        # tra mon i ve ghe re nhat
    sys.stdout.write("%d\n%d\n" % (total, last))

main()

Không gian$O(\sum m_i + K)$

Thời gian$O(\sum m_i \log + K \log K)$

Một hướng khác cũng được trọn điểm

Chặt nhị phân giá $T$ của mâm thứ $K$: đếm số mâm có giá $\le T$ bằng DFS, dừng ngay khi đếm đủ $K$. Để mỗi lần đếm chỉ tốn $O(K)$, DFS cũng phải duyệt các món theo $d$ tăng dần và dừng vòng lặp ngay khi $d$ vượt ngân sách còn lại — lại là ý "sắp theo độ chênh". Tổng tiền = tổng các mâm có giá $< T$ cộng $T$ nhân số mâm còn thiếu.

Đừng quên long long

Một mâm có thể đắt tới $2 \cdot 10^5 \cdot 10^8 = 2 \cdot 10^{13}$, tổng $K$ mâm tới cỡ $4 \cdot 10^{18}$ — vừa khít long long.

C++▶ Chạy tay từng dòng codeSắp giá, sắp các món theo d, rồi lấy K − 1 lần từ hàng đợi ưu tiên.

Dữ liệu vào (stdin) – sửa thoải mái4 6 3 10 5 12 3 7 11 3 2 4 9 3 1 7 10

Dữ liệu mẫu:

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

2using namespace std;

3typedef long long ll;

4struct St { ll s; int i, j; };

5struct Cmp { bool operator()(const St& x, const St& y) const { return x.s > y.s; } };

6int main() {

7 int n, K;

8 scanf("%d %d", &n, &K);

9 vector<vector<ll>> g; // cac mon co tu 2 ghe tro len

10 ll base = 0; // mam re nhat: mon nao cung chon ghe re nhat

11 for (int i = 0; i < n; i++) {

12 int m; scanf("%d", &m);

13 vector<ll> c(m);

14 for (auto& x : c) scanf("%lld", &x);

15 sort(c.begin(), c.end());

16 base += c[0];

17 if (m >= 2) g.push_back(c);

18 }

19 // sap cac mon theo do chenh d = c[1] - c[0] tang dan

20 sort(g.begin(), g.end(), [](const vector<ll>& x, const vector<ll>& y) { return x[1] - x[0] < y[1] - y[0]; });

21 int M = g.size();

22 auto d = [&](int i) { return g[i][1] - g[i][0]; };

23 // trang thai (s, i, j): mon i dang chon ghe j >= 1, cac mon sau i chon ghe re nhat

24 priority_queue<St, vector<St>, Cmp> pq;

25 ll total = base, last = base;

26 if (M > 0) pq.push({base + d(0), 0, 1});

27 for (int cnt = 1; cnt < K; cnt++) {

28 St t = pq.top(); pq.pop();

29 total += t.s; last = t.s;

30 int i = t.i, j = t.j;

31 if (j + 1 < (int)g[i].size()) pq.push({t.s - g[i][j] + g[i][j + 1], i, j + 1}); // mon i doi sang ghe dat hon ke tiep

32 if (i + 1 < M) {

33 pq.push({t.s + d(i + 1), i + 1, 1}); // giu mon i, mon i+1 doi sang ghe thu hai

34 if (j == 1) pq.push({t.s - d(i) + d(i + 1), i + 1, 1}); // tra mon i ve ghe re nhat

35 }

36 }

37 printf("%lld\n%lld\n", total, last);

38}

ChậmVừaNhanhRất nhanh

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

Bộ test có 38 test (8 – 7 – 8 – 7 – 8 theo subtask). Các test lớn có $\sum m_i = 2 \cdot 10^5$, $K = 2 \cdot 10^5$, đáp án tới cỡ $1{,}5 \cdot 10^{18}$. Giá được sinh theo nhiều kiểu: ngẫu nhiên, các ghe bán sát giá nhau, giá rất nhỏ trùng nhau nhiều, độ chênh trải từ rất nhỏ tới rất lớn, hai ghe rẻ nhất cùng giá, và kiểu "ghe thứ ba chỉ đắt hơn ghe thứ hai chút ít" để lộ lỗi thiếu điều kiện $j = 1$. Mọi test subtask 5 có hàng chục nghìn món nhiều ghe nên cách "sinh N con" chắc chắn quá giờ.

Cách làm	Sub 1	Sub 2	Sub 3	Sub 4	Sub 5	Điểm
Cách 1 – liệt kê mọi mâm	8/8	RE/TLE	RE/TLE	TLE	TLE	10
Cách 2 – hai món: heap trên cặp	8/8	7/7	RE/TLE	TLE	TLE	25
Cách 3 – cây N con	8/8	7/7	8/8	TLE	TLE	45
Cách 4 – hai ghe: thêm/thay	8/8	7/7	8/8	7/7	TLE	70
Cách 5 – cây 3 con (lời giải đầy đủ)	8/8	7/7	8/8	7/7	8/8	100
Đối chứng – chặt nhị phân + DFS đếm	8/8	7/7	8/8	7/7	8/8	100
Sai: thiếu điều kiện j = 1 khi "thay"	5/8	3/7	5/8	7/7	3/8	61,43
Sai: quên sắp các món theo d	5/8	6/7	0/8	0/7	0/8	19,11
Sai: "K mâm rẻ nhất chỉ đổi một món"	4/8	2/7	0/8	0/7	0/8	9,29
Sai: tổng tiền kiểu int	2/8	1/7	1/8	0/7	0/8	7,14

Để ý: ví dụ trong đề được chọn sao cho cả bốn lời giải sai ở trên đều in đúng 105 và 20 — sáu mâm rẻ nhất tình cờ đều chỉ đổi một món, các món chưa sắp theo $d$ nhưng thứ tự lấy ra vẫn không bị ảnh hưởng, và mâm "ma" do thiếu điều kiện $j = 1$ (nếu có) đều đắt hơn mâm thứ sáu.

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: lời giải chuẩn chạy tối đa khoảng 0,2 giây (giới hạn 1 giây); các ô TLE đều chạy quá 3 giây, ô RE là do cấp phát quá bộ nhớ khi số mâm quá lớn. Lời giải chuẩn được đối chiếu với chương trình liệt kê vét cạn trên 800 test nhỏ, và với lời giải "chặt nhị phân + DFS đếm" cùng Cách 3 trên 300 test vừa, không lệch test nào; bản Python cho kết quả trùng khớp trên mọi test và chỉ tốn khoảng 0,7 giây CPU ngay cả trên CPython.

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 😇