Luogu P1631: Gộp hai dãy số

Bài toán yêu cầu tìm N giá trị nhỏ nhất từ tất cả các tổng có thể tạo ra bằng cách lấy một phần tử từ dãy A và một phần tử từ dãy B. Cả hai dãy A và B đều có độ dài N và đã được sắp xếp tăng dần.

Phương pháp đơn giản nhất là tính tất cả N² tổng và sau đó sắp xếp chúng, nhưng cách này sẽ quá chậm. Chúng ta cần một giải pháp tối ưu hơn.

Giải pháp sử dụng hàng đợi ưu tiên (min-heap)

Do A và B đều được sắp xếp, ta có thể xem các tổng được tạo ra từ một phần tử cố định trong B là một dãy con đã được sắp xếp. Cụ thể, với mỗi B[i], dãy tổng B[i] + A[1], B[i] + A[2], ..., B[i] + A[N] là một dãy tăng dần.

Chúng ta có N dãy con như vậy. Bây giờ, vấn đề trở thành tìm N phần tử nhỏ nhất từ N dãy con đã sắp xếp. Đây là một bài toán kinh điển có thể giải quyết hiệu quả bằng hàng đợi ưu tiên (min-heap).

Thuật toán:

1. Khởi tạo một hàng đợi ưu tiên (min-heap). Đưa phần tử đầu tiên của mỗi dãy con vào heap, tức là các giá trị A[1] + B[i] (với i từ 1 đến N).
2. Lặp N lần:
   1. Lấy phần tử nhỏ nhất từ heap và in ra. Đây là một trong N giá trị tổng nhỏ nhất cần tìm.
   2. Lấy chỉ số của dãy con mà phần tử này thuộc về. Đưa phần tử tiếp theo của dãy con đó (A[cur+1] + B[i]) vào heap.

Độ phức tạp thời gian của thuật toán này là O(N log N), vì mỗi lần chèn và lấy ra từ heap mất O(log N) và chúng ta thực hiện các thao tác này tổng cộng 2N lần.

Mã nguồn C++:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// Hàm đọc số nguyên nhanh
inline int docSoNhanh() {
    int num = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        num = num * 10 + c - '0';
        c = getchar();
    }
    return num;
}

int main() {
    int n;
    n = docSoNhanh();

    vector<int> dayA(n + 1), dayB(n + 1);
    for (int i = 1; i <= n; ++i) dayA[i] = docSoNhanh();
    for (int i = 1; i <= n; ++i) dayB[i] = docSoNhanh();

    // Hàng đợi ưu tiên lưu cặp (tổng, chỉ số dãy con)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> hangDoiUuTien;

    // Khởi tạo heap với phần tử đầu tiên của mỗi dãy con
    for (int i = 1; i <= n; ++i) {
        hangDoiUuTien.push({dayA[1] + dayB[i], i});
    }

    // Lấy N giá trị nhỏ nhất
    for (int i = 1; i <= n; ++i) {
        auto [tongHienTai, chiSoDday] = hangDoiUuTien.top();
        hangDoiUuTien.pop();
        cout << tongHienTai << " ";

        // Đưa phần tử tiếp theo của dãy con tương ứng vào heap
        if (chiSoDday + 1 <= n) {
            hangDoiUuTien.push({tongHienTai - dayA[chiSoDday] + dayA[chiSoDday + 1], chiSoDday + 1});
        }
    }

    return 0;
}

Luogu P2085: Tìm giá trị hàm nhỏ nhất

Bài toán yêu cầu với N hàm bậc hai f_i(x) = a_i * x² + b_i * x + c_i, hãy tìm m giá trị nhỏ nhất trong tất cả các giá trị hàm khi x là số nguyên dương.

Giải pháp cho bài toán này tương tự như bài toán trên.

Giải pháp:

Mỗi hàm f_i(x) tạo ra một dãy giá trị vô hạn, tăng dần: f_i(1), f_i(2), f_i(3), ... . Chúng ta cần tìm m giá trị nhỏ nhất từ hợp của N dãy này.

Chúng ta có thể áp dụng cùng một chiến lược với hàng đợi ưu tiên:

1. Khởi tạo một min-heap. Đưa giá trị đầu tiên của mỗi hàm, tức là f_i(1), vào heap.
2. Lặp m lần:
   1. Lấy giá trị nhỏ nhất từ heap và in ra.
   2. Đưa giá trị tiếp theo của hàm tương ứng (f_i(x+1)) vào heap.

Mã nguồn C++:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

// Hàm đọc số nguyên nhanh
inline int docSoNhanh() {
    int num = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') {
        num = num * 10 + c - '0';
        c = getchar();
    }
    return num;
}

int main() {
    int soHam, soGiaTriCanTim;
    soHam = docSoNhanh();
    soGiaTriCanTim = docSoNhanh();

    vector<vector<int>> heSoHam(soHam + 1, vector<int>(3));
    for (int i = 1; i <= soHam; ++i) {
        heSoHam[i][0] = docSoNhanh(); // a_i
        heSoHam[i][1] = docSoNhanh(); // b_i
        heSoHam[i][2] = docSoNhanh(); // c_i
    }

    // Hàng đợi ưu tiên lưu cặp (giá trị hàm, chỉ số hàm)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> hangDoiUuTien;

    // Khởi tạo heap với giá trị f_i(1) cho mỗi hàm
    for (int i = 1; i <= soHam; ++i) {
        hangDoiUuTien.push({heSoHam[i][0] + heSoHam[i][1] + heSoHam[i][2], i});
    }

    // Lấy m giá trị nhỏ nhất
    for (int i = 1; i <= soGiaTriCanTim; ++i) {
        auto [giaTriHienTai, chiSoHam] = hangDoiUuTien.top();
        hangDoiUuTien.pop();
        cout << giaTriHienTai << " ";

        // Tăng x và tính giá trị hàm tiếp theo
        hangDoiUuTien.push({heSoHam[chiSoHam][0] * (i + 1) * (i + 1) + heSoHam[chiSoHam][1] * (i + 1) + heSoHam[chiSoHam][2], chiSoHam});
    }

    return 0;
}