Hiểu bài toán

Một đội tuyển có n học sinh, mỗi học sinh có hệ số kỹ năng ban đầu ai và chỉ số thông minh bi. Giáo viên có thể làm việc tối đa c lần với học sinh. Mỗi lần làm việc với học sinh i, kỹ năng của học sinh đó tăng thêm b_i. Một học sinh được giải khi kỹ năng >= k. Yêu cầu tìm số lượng học sinh tối đa có thể được giải.

Quan sát:

• Nếu a_i >= k, học sinh này đã được giải ngay từ đầu, không cần làm việc.
• Nếu ai < k:
  • Nếu bi = 0, kỹ năng không tăng, không thể đạt k.
  • Nếu bi > 0, cần t lần làm việc để kỹ năng >= k, với t = ceil((k - ai) / b_i).

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

Cách Sắp xếp tăng dần theo số lần cần thiết

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;

int n, c, k;
pair<int, int> a[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> c >> k;
    vector<int> need;
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
        if (a[i].first >= k)
            ++ans;
        else if (a[i].second > 0)
            need.push_back((k - a[i].first + a[i].second - 1) / a[i].second);
    }
    sort(need.begin(), need.end());
    long long used = 0;
    for (int x : need) {
        if (used + x <= c) {
            used += x;
            ++ans;
        }
        else
            break;
    }
    cout << ans;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Cách tiếp cận này chia học sinh thành 3 loại:

1. Đã đủ kỹ năng (a_i >= k): Tăng trực tiếp vào kết quả.
2. Có thể cải thiện (ai < k và bi > 0): Tính số lần cần thiết t = ceil((k - ai) / bi) và lưu vào vector need.
3. Không thể cải thiện (ai < k và bi = 0): Bỏ qua.

Sau đó, ta sắp xếp need tăng dần. Đây là bài toán chọn đồ vật kinh điển (Greedy): để tối đa hóa số lượng học sinh được giải với ngân sách c, ta nên ưu tiên những học sinh cần ít công sức nhất (số lần làm việc ít nhất). Ta lần lượt chọn các học sinh trong need cho đến khi hết ngân sách.

Độ phức tạp đến từ việc sắp xếp vector need có kích thước tối đa N, là O(N log N).

Cách Tối ưu hóa bộ nhớ (Không dùng vector)

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, c, k, a, b, q[11234567], t, tt, d = 0, j = 1;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> c >> k;
    for (ll i = 1; i <= n; i++) {
        cin >> a >> b;
        if (b == 0 && a < k) q[i] = -1;
        else if (a >= k) q[i] = 0;
        else {
            t = k - a;
            tt = t / b;
            if (t % b != 0) tt++;
            q[i] = tt;
        }
    }
    sort(q + 1, q + n + 1);
    while (c != 0 && j <= n) {
        if (q[j] == 0) d++;
        else if (q[j] != -1 && c - q[j] >= 0) {
            d++; c -= q[j];
        }
        else if (c - q[j] < 0) break;
        j++;
    }
    cout << d;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Về cơ bản giống cách tiếp cận 1, nhưng thay vì dùng vector<pair> hoặc vector động, giải pháp này dùng mảng tĩnh lớn (q[11234567]) để lưu trữ số lần cần thiết. Việc này có thể giúp tránh overhead của vector và tối ưu một chút về bộ nhớ trong một số trường hợp, nhưng về tổng thể độ phức tạp vẫn giữ nguyên do phụ thuộc vào hàm sort. Logic xử lý các trường hợp ai >= k, bi = 0 và ai < k, bi > 0 là tương tự nhau.

Cách Cải tiến (Loại bỏ học sinh bất khả thi)

#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std;
ll n, c, k;
pii a[N];

void solve() {
   cin >> n >> c >> k;
   for (int i = 1; i <= n; i++) {
        cin >> a[i].fi >> a[i].se;
   }
   ll cnt = 0;
   vector<ll> vec;
   for (int i = 1; i <= n; i++) {
        if (a[i].fi >= k) {
            cnt++; // Tăng số lượng được giải ngay lập tức
        } else {
            if (!a[i].se) { // b_i == 0
                continue; // Loại bỏ hoàn toàn
            }
            // Tính số lần cần thiết
            ll need = (k - a[i].fi + a[i].se - 1) / a[i].se;
            if (need <= c) { // Optimization: Chỉ lưu những đứa có cơ hội
                 vec.push_back(need);
            }
        }
   }
   sort(vec.begin(), vec.end());
   for (ll x : vec) {
        if (c >= x) {
            c -= x;
            cnt++;
        } else {
            break;
        }
   }
   cout << cnt << endl;
}

int main() {
    solve();
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Đây là phiên bản chi tiết của giải pháp Greedy. Nó chính xác là thuật toán chuẩn:

1. Đếm ngay những học sinh có a_i >= k.
2. Với học sinh có ai < k:
   • Nếu bi = 0, loại bỏ.
   • Nếu b_i > 0, tính need. Nếu need > c (ngân sách tối đa), ta có thể cân nhắc loại bỏ luôn học sinh này ngay từ đầu vì dù có dùng hết ngân sách cũng không đủ. Tuy nhiên, trong bài toán tối đa hóa số lượng, ta chỉ cần sort và chọn những đứa nhỏ nhất, nên lọc bớt need > c chỉ là tối ưu bộ nhớ, không thay đổi logic.
3. Sắp xếp need và chọn Greedy.

Giải pháp này làm rõ các bước xử lý điều kiện.

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

Bài học kinh nghiệm

• Bài toán có tính chất Quy hoạch động hoặc Greedy. Do yêu cầu tối đa hóa số lượng (chỉ quan tâm đến số lượng đạt giải) và chi phí cho mỗi học sinh là độc lập, đây là bài toán 'Cái túi' đơn giản (Knapsack) hoặc bài toán 'Chọn đồ vật kinh điển' (Greedy): ưu tiên những cái rẻ nhất.
• Công thức tính số lần làm việc: t = (k - a_i + b_i - 1) / b_i. Đây là cách tính số nguyên dương nhỏ nhất sao cho t * b_i >= k - a_i.
• Các trường hợp đặc biệt: ai >= k (không tốn chi phí), bi = 0 (không thể cải thiện).

Lỗi thường gặp

• Kiểu dữ liệu: k, c, a_i, b_i lên tới 10^9, phép nhân hoặc cộng có thể vượt quá 32-bit. Nên dùng long long (64-bit) cho các biến tính toán và lưu trữ.
• Xử lý chia lấy dư khi tính số lần cần thiết: Sai nếu dùng (k - a_i) / b_i mà không cộng thêm khi k - a_i không chia hết cho b_i.
• Trường hợp b_i = 0: Cần kiểm tra riêng, tránh chia cho 0 hoặc tính toán sai.