Hướng dẫn giải của Xưởng cơ khí_PY

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, 111_LeQuangTam, sussyboy, asenen_kiet

Hiểu bài toán

Bài toán yêu cầu chọn một tập hợp các đơn hàng từ N đơn hàng cho trước để tối đa hóa tổng tiền công thu được. Mỗi đơn hàng i có hai thông số: thời điểm phải hoàn thành (deadline) t[i] và tiền công x[i]. Các đơn hàng phải được thực hiện tuần tự, mỗi đơn hàng tốn 1 đơn vị thời gian. Đơn hàng chỉ có thể được thực hiện nếu thời điểm hoàn thành không vượt quá deadline của nó. Nói cách khác, nếu ta chọn k đơn hàng, thời điểm hoàn thành đơn hàng thứ j phải nhỏ hơn hoặc bằng deadline của đơn hàng đó.

Các cách tiếp cận

Cách Quy hoạch động (Dynamic Programming)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Order {
    int t, x;
};

int main() {
    freopen("xck.inp", "r", stdin);
    freopen("xck.out", "w", stdout);

    int N;
    cin >> N;
    vector<Order> orders(N);
    int max_deadline = 0;
    for (int i = 0; i < N; ++i) {
        cin >> orders[i].t >> orders[i].x;
        max_deadline = max(max_deadline, orders[i].t);
    }

    // DP[i] là tổng tiền công lớn nhất có thể có khi thực hiện i đơn hàng
    // Kích thước mảng DP là max_deadline + 1
    vector<long long> DP(max_deadline + 1, 0);

    // Sắp xếp đơn hàng theo deadline tăng dần để xử lý
    sort(orders.begin(), orders.end(), [](const Order& a, const Order& b) {
        return a.t < b.t;
    });

    for (const auto& order : orders) {
        // Duyệt ngược để tránh dùng lại đơn hàng đang xét
        for (int j = order.t; j >= 1; --j) {
            DP[j] = max(DP[j], DP[j-1] + order.x);
        }
    }

    long long ans = 0;
    for (int i = 1; i <= max_deadline; ++i) ans = max(ans, DP[i]);
    cout << ans;
    return 0;
}
  • Time Complexity: O(N * T_max)
  • Space Complexity: O(T_max)

Cách tiếp cận này sử dụng quy hoạch động. Ta định nghĩa DP[j] là tổng tiền công lớn nhất có thể đạt được khi thực hiện đúng j đơn hàng. Với mỗi đơn hàng, ta cập nhật mảng DP từ order.t về 1. Logic là để chọn đơn hàng này vào vị trí thứ j, ta phải có tổng tiền công của j-1 đơn hàng trước đó và đơn hàng này phải hoàn thành trước hoặc đúng deadline của nó. Độ phức tạp phụ thuộc vào tổng deadline tối đa, phù hợp khi deadline nhỏ.

Cách Greedy với Priority Queue (Sử dụng Heap)
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int main() {
    freopen("xck.inp", "r", stdin);
    freopen("xck.out", "w", stdout);

    int N;
    cin >> N;
    vector<pair<int, int>> orders(N);
    for (int i = 0; i < N; ++i) {
        cin >> orders[i].first >> orders[i].second;
    }

    // Sắp xếp theo deadline tăng dần
    sort(orders.begin(), orders.end());

    // Min-heap chứa tiền công của các đơn hàng đã chọn
    priority_queue<int, vector<int>, greater<int>> minHeap;

    for (const auto& order : orders) {
        int t = order.first;
        int x = order.second;

        // Nếu số lượng đơn hàng đang chọn nhỏ hơn deadline,
        // ta có thể thêm đơn hàng này vào.
        // Tạm thời cho vào heap, sau này nếu cần có thể loại bỏ.
        if (minHeap.size() < t) {
            minHeap.push(x);
        } else {
            // Nếu heap đã đầy (tức là đang chọn đúng t đơn hàng,
            // hoặc nhiều hơn nhưng chỉ quan tâm đến t nhỏ nhất)
            // Ta so sánh với đơn hàng có tiền công nhỏ nhất trong tập đã chọn.
            // Nếu đơn hàng hiện tại có tiền công lớn hơn, ta thay thế nó.
            if (!minHeap.empty() && minHeap.top() < x) {
                minHeap.pop();
                minHeap.push(x);
            }
        }
    }

    long long totalProfit = 0;
    while (!minHeap.empty()) {
        totalProfit += minHeap.top();
        minHeap.pop();
    }

    cout << totalProfit;
    return 0;
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)

Thuật toán Greedy này rất hiệu quả.

  1. Sắp xếp các đơn hàng theo deadline tăng dần.
  2. Duyệt qua từng đơn hàng, duy trì một Min-heap chứa các đơn hàng đã chọn.
  3. Nếu số lượng đơn hàng trong heap nhỏ hơn deadline của đơn hàng hiện tại, ta thêm nó vào.
  4. Nếu heap đã có số lượng bằng deadline, ta chỉ có thể chọn thêm nếu loại bỏ được một đơn hàng có tiền công thấp hơn để nhường chỗ (vì số lượng đơn hàng không thể vượt quá deadline). Cách này đảm bảo ta luôn giữ lại các đơn hàng có tiền công cao nhất trong khả năng đáp ứng deadline.
Cách Greedy với Disjoint Set Union (DSU)
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

struct Order {
    int t, x;
};

// Mảng cha cho DSU
vector<int> parent;

// Tìm nguồn (thời điểm trống gần nhất)
int findSet(int i) {
    if (parent[i] == i)
        return i;
    return parent[i] = findSet(parent[i]);
}

// Gộp hai tập hợp (khi một thời điểm bị chiếm, trỏ đến thời điểm trước đó)
void unionSets(int i, int j) {
    int root_i = findSet(i);
    int root_j = findSet(j);
    if (root_i != root_j) {
        parent[root_i] = root_j;
    }
}

int main() {
    freopen("xck.inp", "r", stdin);
    freopen("xck.out", "w", stdout);

    int N;
    cin >> N;
    vector<Order> orders(N);
    int max_deadline = 0;
    for (int i = 0; i < N; ++i) {
        cin >> orders[i].t >> orders[i].x;
        max_deadline = max(max_deadline, orders[i].t);
    }

    // Sắp xếp theo tiền công giảm dần
    sort(orders.begin(), orders.end(), [](const Order& a, const Order& b) {
        return a.x > b.x;
    });

    // DSU: parent[i] là thời điểm trống gần nhất <= i
    parent.resize(max_deadline + 1);
    iota(parent.begin(), parent.end(), 0);

    long long ans = 0;
    for (const auto& order : orders) {
        int available_slot = findSet(order.t);
        if (available_slot > 0) {
            ans += order.x;
            // Sau khi chiếm slot này, nó không còn trống nữa.
            // Gộp nó với slot trước đó (available_slot - 1)
            unionSets(available_slot, available_slot - 1);
        }
    }

    cout << ans;
    return 0;
}
  • Time Complexity: O(N log N hoặc N * α(N))
  • Space Complexity: O(T_max)

Đây là cách tiếp cận tối ưu nhất về mặt lý thuyết.

  1. Sắp xếp các đơn hàng theo tiền công giảm dần.
  2. Với mỗi đơn hàng, ta cố gắng đặt nó vào thời điểm muộn nhất có thể không vượt quá deadline (tức là đúng deadline hoặc muộn hơn một chút nhưng trước deadline).
  3. Sử dụng DSU để tìm kiếm thời điểm trống nhanh chóng. Nếu một đơn hàng có deadline là t, ta tìm slot trống <= t. Nếu tìm thấy, cộng tiền công và "đánh dấu" slot đó đã đầy bằng cách nối nó với slot t-1. Lần sau khi tìm slot cho deadline t, ta sẽ nhảy về t-1. Cách này đảm bảo luôn chọn được đơn hàng có tiền công cao nhất và đặt vào vị trí phù hợp nhất.

Phân tích độ phức tạp

Cách tiếp cận Time Space Tên
1 O(N * T_max) O(T_max) Quy hoạch động (Dynamic Programming)
2 O(N log N) O(N) Greedy với Priority Queue (Sử dụng Heap)
3 O(N log N hoặc N * α(N)) O(T_max) Greedy với Disjoint Set Union (DSU)

Bài học kinh nghiệm

  • Vấn đề có thể được xem là bài toán 'Kỳ thi' (Exam Problem) kinh điển: chọn nhiều nhất có thể các công việc có deadline, nhưng ở đây ta tối đa hóa trọng số (tiền công) chứ không chỉ số lượng.
  • Việc sắp xếp các đơn hàng là chìa khóa của các thuật toán hiệu quả. Sắp xếp theo deadline tăng dần giúp giải quyết theo trình tự thời gian, sắp xếp theo tiền công giảm dần giúp ưu tiên các đơn hàng quan trọng trước.
  • Thuật toán Greedy với Priority Queue là lời giải kinh điển cho các bài toán tối ưu hóa có ràng buộc về thời gian và số lượng.

Lỗi thường gặp

  • Quên trừ đi chỉ số mảng bắt đầu từ 0 hoặc 1 khi xử lý deadline (ví dụ: deadline 5 có thể thực hiện vào các thời điểm 1, 2, 3, 4, 5).
  • Sử dụng biến long long cho kết quả cuối cùng để tránh tràn số khi tổng tiền công lớn.
  • Trong thuật toán DSU, cần xử lý trường hợp available_slot == 0 (không còn slot trống) để không truy cập mảng ngoài biên.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.