Hướng dẫn giải của Câu 4 (Tuyển sinh chuyên Tin Bình Dương 2022-2023)


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.

Hướng dẫn giải

Có N khách hàng (N < 500). Bán được cho khách i thì công ty được lợi nhuận Ki và có Ci cơ hội bán cho các khách khác. Ban đầu công ty đã bán được cho một khách hàng. Cần tìm lợi nhuận lớn nhất có thể đạt được.

Mô hình: gọi S là tập các khách đã bán được. Mỗi lần bán thêm tốn 1 cơ hội và nhận thêm Cj cơ hội của khách j. Có thể chứng minh S khả thi khi và chỉ khi 1 + sum{i in S}(Ci - 1) >= 0 (tức là đủ cơ hội cho cả tập S, và có thể sắp thứ tự bán các khách có C >= 1 trước, khách có C = 0 sau). Bài toán trở thành: chọn tập S sao cho điều kiện trên đúng và tổng Ki trên S là lớn nhất.

Nhận xét: khách có C >= 1 thì luôn nên chọn (lợi nhuận K >= 0 và không làm giảm cơ hội nhiều hơn số cơ hội họ mang lại). Khách có C = 0 làm mất đúng 1 cơ hội, nên chỉ chọn tối đa B khách có lợi nhuận lớn nhất, với B = 1 + sum{Ci >= 1}(C_i - 1).

Sub 1: Vét cạn — ~O(2^n \cdot n)~, dùng khi ~n \le 20~

Thử mọi tập con khác rỗng S của khách hàng, tính ngân sách cơ hội và tổng lợi nhuận, nếu thỏa điều kiện thì cập nhật đáp án lớn nhất.

Chấm riêng sub này: đúng 10/30 test (các test có n <= 20 đều đúng).

Sub 2: Tham lam — ~O(n \log n)~, dùng cho mọi n
  • Lấy tất cả khách có C >= 1, cộng lợi nhuận K và cộng B thêm (C - 1).
  • Sắp các khách có C = 0 theo K giảm dần, lấy tối đa B khách đầu tiên.

Ví dụ: 5 khách (K, C) = (0,0), (2,0), (2,0), (3,0), (5,1). Khách có C >= 1 chỉ có (5,1): lợi nhuận 5, B = 1 + 0 = 1. Khách C = 0 có K = 3 lớn nhất, lấy 1 khách: 5 + 3 = 8.

Bẫy: B không âm và có thể lớn, dùng long long. Đáp án không vượt quá 500 · 10^4 nên không tràn.

Chương trình hoàn chỉnh

main đọc N và các cặp (K, C), nếu n <= 20 gọi sub1, còn lại gọi sub2.

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

int n;
long long K[505];  // lợi nhuận khi bán được cho khách i
long long C[505];  // số cơ hội bán cho các khách khác sau khi bán được cho khách i

// Mô hình: công ty đã bán cho khách i0 (chọn tùy ý), khi đó có C[i0] cơ hội.
// Mỗi lần bán thêm cho khách j tốn 1 cơ hội và được thêm C[j] cơ hội.
// Tập S các khách bán được (khác rỗng) khả thi khi và chỉ khi 1 + sum_{i in S}(C[i] - 1) >= 0.
// Cần tối đa tổng K[i] với i trong S.

// Sub 1: vét cạn — thử mọi tập khách hàng S (bitmask), kiểm tra điều kiện, lấy tổng K lớn nhất. O(2^n * n). Dùng khi n <= 20.
void sub1() {
    long long best = 0;
    for (int mask = 1; mask < (1 << n); mask++) {
        long long budget = 1, profit = 0;
        for (int i = 0; i < n; i++)
            if (mask >> i & 1) {
                budget += C[i] - 1;
                profit += K[i];
            }
        if (budget >= 0) best = max(best, profit);
    }
    cout << best << "\n";
}

// Sub 2: tham lam. Mọi khách có C >= 1 đều nên lấy (lấy thêm chỉ làm tăng cơ hội hoặc giữ nguyên, lợi nhuận >= 0).
// Khách có C = 0 làm mất 1 cơ hội mỗi người, nên lấy tối đa B người có lợi nhuận lớn nhất,
// với B = 1 + sum_{C[i] >= 1}(C[i] - 1). O(n log n).
void sub2() {
    long long profit = 0, budget = 1;
    vector<long long> zero;  // lợi nhuận của các khách có C = 0
    for (int i = 0; i < n; i++) {
        if (C[i] >= 1) {
            profit += K[i];
            budget += C[i] - 1;
        } else {
            zero.push_back(K[i]);
        }
    }
    sort(zero.rbegin(), zero.rend());  // giảm dần
    for (long long i = 0; i < (long long)zero.size() && i < budget; i++)
        profit += zero[i];
    cout << profit << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> K[i] >> C[i];
    if (n <= 20) sub1();  // dữ liệu nhỏ: vét cạn
    else sub2();          // tham lam
    return 0;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


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