Tóm tắt đề bài

Có \(n\) khách hàng xếp hàng mua bánh. Khách hàng thứ \(i\) muốn mua \(a_i\) chiếc bánh và chỉ sẵn sàng chờ tối đa \(t_i\) phút. Thời gian phục vụ mỗi khách là \(1\) phút. Cửa hàng phục vụ theo đúng thứ tự xếp hàng nhưng có thể từ chối phục vụ bất kỳ ai. Một khách hàng được phục vụ nếu thời điểm bắt đầu phục vụ họ không quá \(t_i\). Tìm tổng số bánh lớn nhất có thể bán được.

Phân tích

• Điều kiện: \(n \le 10^4, t_i \le 10^4, a_i \le 10^5\).
• Nhận xét quan trọng:
  • Giả sử chúng ta chọn phục vụ một tập hợp các khách hàng. Để phục vụ được nhiều bánh nhất, ta cần sắp xếp họ theo đúng thứ tự ban đầu (vì đề bài yêu cầu phục vụ theo đúng thứ tự xếp hàng).
  • Nếu ta chọn phục vụ \(k\) khách hàng, khách hàng được chọn thứ \(j\) (\(1 \le j \le k\)) sẽ được phục vụ tại thời điểm \(j-1\). Do đó, điều kiện để khách hàng này không bỏ đi là \(j-1 \le t_i\), hay \(j \le t_i + 1\).
  • Điều này có nghĩa là: Nếu ta chọn một nhóm khách hàng, khách hàng thứ \(i\) trong danh sách ban đầu nếu được chọn và là người thứ \(j\) được phục vụ, thì \(j\) phải thỏa mãn \(j \le t_i + 1\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Sử dụng quy hoạch động. Gọi \(dp[i][j]\) là số bánh lớn nhất bán được khi xét đến khách hàng thứ \(i\) và đã phục vụ được \(j\) khách hàng.

• Nếu không phục vụ khách thứ \(i\): \(dp[i][j] = dp[i-1][j]\)
• Nếu phục vụ khách thứ \(i\): Điều kiện là \(j-1 \le t_i\) (vì khách \(i\) là người thứ \(j\) được phục vụ, bắt đầu tại thời điểm \(j-1\)).
  • \(dp[i][j] = \max(dp[i][j], dp[i-1][j-1] + a_i)\)

Độ phức tạp

• Thời gian: \(O(n^2)\) do có 2 vòng lặp lồng nhau.
• Bộ nhớ: \(O(n^2)\) hoặc \(O(n)\) nếu tối ưu mảng một chiều.
• Đánh giá: Với \(n = 10^4\), \(O(n^2)\) rơi vào khoảng \(10^8\) phép tính, có thể kịp trong giới hạn thời gian nếu cài đặt tối ưu, nhưng có cách tiếp cận hiệu quả hơn bằng cấu trúc dữ liệu.

Code Brute Force

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1), t(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> t[i];
    }

    // dp[j] là số bánh lớn nhất bán được cho j khách hàng
    vector<long long> dp(n + 2, -1);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = i; j >= 1; j--) {
            if (j - 1 <= t[i] && dp[j - 1] != -1) {
                dp[j] = max(dp[j], dp[j - 1] + a[i]);
            }
        }
    }

    long long ans = 0;
    for (int j = 0; j <= n; j++) {
        ans = max(ans, dp[j]);
    }
    cout << ans;
    return 0;
}

import sys

def solve():
    n = int(sys.stdin.readline())
    customers = []
    for _ in range(n):
        customers.append(list(map(int, sys.stdin.readline().split())))

    # dp[j] là số bánh lớn nhất bán được cho j khách hàng
    dp = [-1] * (n + 1)
    dp[0] = 0

    for i in range(n):
        a_i, t_i = customers[i]
        for j in range(i + 1, 0, -1):
            if j - 1 <= t_i and dp[j-1] != -1:
                dp[j] = max(dp[j], dp[j-1] + a_i)

    print(max(dp))

solve()

Hướng giải quyết (Tối ưu)

Nhận xét

Thay vì dùng quy hoạch động, ta có thể sử dụng chiến thuật tham lam kết hợp với hàng đợi ưu tiên (Priority Queue):

1. Duyệt qua từng khách hàng từ \(1\) đến \(n\).
2. Với mỗi khách hàng \(i\), ta tạm thời "giả định" sẽ phục vụ họ. Thêm \(a_i\) vào một hàng đợi ưu tiên (min-heap) và cộng \(a_i\) vào tổng số bánh.
3. Sau khi thêm khách hàng \(i\), số lượng khách hàng đang được chọn phục vụ là pq.size().
4. Nếu số lượng khách hàng vượt quá giới hạn chờ của khách hàng hiện tại (tức là pq.size() > t_i + 1), ta bắt buộc phải loại bỏ một khách hàng đã chọn trước đó để đảm bảo tính hợp lệ.
5. Để tổng số bánh là lớn nhất, ta sẽ loại bỏ khách hàng có số lượng bánh \(a_j\) nhỏ nhất trong số các khách đã chọn (đó là lý do dùng min-heap).

Tại sao cách này đúng?

Mặc dù đề bài yêu cầu phục vụ theo đúng thứ tự, nhưng điều kiện \(j \le t_i + 1\) chỉ phụ thuộc vào số lượng khách hàng được phục vụ trước khách hàng \(i\). Khi ta loại bỏ một khách hàng có \(a_j\) nhỏ nhất, ta giải phóng một "vị trí thời gian" cho các khách hàng phía sau mà không làm vi phạm điều kiện của các khách hàng đã chọn (vì việc loại bỏ chỉ làm giảm số thứ tự phục vụ của các khách đứng sau khách bị loại).

Độ phức tạp

• Thời gian: \(O(n \log n)\) do mỗi khách hàng được đẩy vào và lấy ra khỏi Priority Queue tối đa một lần.
• Bộ nhớ: \(O(n)\) để lưu trữ Priority Queue và dữ liệu khách hàng.

Code tham khảo

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

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // Sử dụng priority_queue để lưu số bánh của các khách hàng đã chọn
    // priority_queue mặc định là max-heap, dùng greater để biến thành min-heap
    priority_queue<int, vector<int>, greater<int>> pq;
    long long total_cakes = 0;

    for (int i = 0; i < n; i++) {
        int a, t;
        cin >> a >> t;

        // Tạm thời chọn khách hàng này
        pq.push(a);
        total_cakes += a;

        // Nếu số người được chọn vượt quá thời gian chờ cho phép (t + 1)
        // thì loại bỏ người mua ít bánh nhất trong danh sách đã chọn
        if (pq.size() > (size_t)t + 1) {
            total_cakes -= pq.top();
            pq.pop();
        }
    }

    cout << total_cakes << endl;

    return 0;
}

import sys
import heapq

def solve():
    # Đọc n từ dòng đầu tiên
    line1 = sys.stdin.readline()
    if not line1:
        return
    n = int(line1.strip())

    pq = [] # Min-heap lưu số lượng bánh của các khách hàng được chọn
    total_cakes = 0

    for _ in range(n):
        line = sys.stdin.readline().split()
        if not line:
            break
        a_i, t_i = map(int, line)

        # Tạm thời thêm khách hàng hiện tại vào danh sách phục vụ
        heapq.heappush(pq, a_i)
        total_cakes += a_i

        # Nếu số lượng khách trong hàng phục vụ vượt quá thời gian chờ t_i + 1
        # Ta loại bỏ khách hàng có số bánh ít nhất
        if len(pq) > t_i + 1:
            min_val = heapq.heappop(pq)
            total_cakes -= min_val

    print(total_cakes)

if __name__ == "__main__":
    solve()