Hướng dẫn giải của Chiến lược cho vay

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, manhduc, HaoNoPro, nguyenvietnhat

Hiểu bài toán

Cho ~m~ sinh viên với số tiền vay tương ứng ~t_1, t_2, ..., t_m~ và ngân sách ~n~. Ngân hàng muốn chọn một tập hợp sinh viên sao cho:

  1. Tổng tiền vay không vượt quá ~n~.
  2. Số lượng sinh viên được vay là lớn nhất có thể.
  3. Trong các cách chọn thỏa mãn điều kiện trên, chọn cách mà số tiền vay ít nhất của sinh viên trong tập hợp là lớn nhất.

Yêu cầu: Với ~Q~ truy vấn (~n_k~), đưa ra số lượng sinh viên (~s~) và số tiền vay ít nhất (~v~) tương ứng.

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

Cách Tham lam với Sliding Window (Two Pointers)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

void solve() {
    int m, Q;
    cin >> m >> Q;
    vector<ll> t(m);
    for (int i = 0; i < m; ++i) cin >> t[i];
    sort(t.begin(), t.end());

    vector<ll> P(m + 1, 0);
    for (int i = 0; i < m; ++i) P[i + 1] = P[i] + t[i];

    while (Q--) {
        ll n_k;
        cin >> n_k;

        // 1. Tim so luong sinh vien toi da (s) bang cach chon nhung nguoi co tien it nhat
        auto it = upper_bound(P.begin(), P.end(), n_k);
        int s = (int)(it - P.begin()) - 1;

        if (s == 0) {
            cout << "0 0\n";
            continue;
        }

        // 2. Tim so tien it nhat lon nhat (v)
        // Kiem tra xem co the chon them nguoi co tien lon hon de thay the nguoi co tien nho hon khong
        ll current_sum = P[s];
        int r = s;

        // Moi buoc, thu them nguoi tiep theo (r + 1) va loai bo nguoi dau tien (r - s + 1)
        while (r + 1 <= m && current_sum + t[r] - t[r - s] <= n_k) {
            current_sum = current_sum + t[r] - t[r - s];
            r++;
        }

        cout << s << " " << t[r - s] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}
  • Time Complexity: O(m log m + Q log m + m) ~ O(m log m + Q log m)
  • Space Complexity: O(m)

Cách tiếp cận này dựa trên quan sát rằng để tối đa hóa số lượng sinh viên, chúng ta nên chọn những người có nhu cầu vay nhỏ nhất. Sau khi xác định được số lượng sinh viên tối đa ~s~, chúng ta cần chọn ~s~ sinh viên sao cho tổng tiền vay ≤ ~n~ và số tiền vay nhỏ nhất trong tập hợp này là lớn nhất.

Bước 1: Sắp xếp mảng ~t~ tăng dần. Tính mảng cộng dồn ~P~. Bước 2: Với mỗi truy vấn ~n_k~, tìm số lượng sinh viên tối đa ~s~ sao cho tổng ~s~ phần tử đầu tiên (nhỏ nhất) ≤ ~n_k~. Đây là giá trị ~s~ tối ưu. Bước 3: Để tìm số tiền vay nhỏ nhất lớn nhất, ta sử dụng kỹ thuật Sliding Window. Ban đầu, ta chọn ~s~ sinh viên đầu tiên. Sau đó, ta thử lần lượt thay thế sinh viên có tiền vay nhỏ nhất bằng sinh viên có tiền vay lớn hơn tiếp theo trong danh sách đã sắp xếp (điểm cuối của cửa sổ trượt sang phải). Nếu việc thêm sinh viên mới và bớt sinh viên cũ vẫn thỏa mãn điều kiện tổng tiền ≤ ~n_k~, ta chấp nhận. Cuối cùng, phần tử đầu tiên của cửa sổ chính là số tiền vay nhỏ nhất lớn nhất có thể đạt được.

Cách Binary Search trên số tiền nhỏ nhất (v)
// Hàm kiểm tra xem có thể chọn được k sinh viên với số tiền tối thiểu là x hay không
bool check(int k, ll x, ll n, const vector<ll>& P) {
    // Tim k phan tu dau tien co tien >= x
    // Neu so luong phan tu co tien >= x du de chon k nguoi
    // Tong tien cua k nguoi do phai <= n
    // Day la bai toan phuc tap, cach nay phu hop hon cho approach 1
    return true; // Placeholder
}

void solve() {
    int m, Q;
    cin >> m >> Q;
    vector<ll> t(m);
    for (int i = 0; i < m; ++i) cin >> t[i];
    sort(t.begin(), t.end());

    vector<ll> P(m + 1, 0);
    for (int i = 0; i < m; ++i) P[i + 1] = P[i] + t[i];

    while (Q--) {
        ll n_k;
        cin >> n_k;

        // 1. Tim so luong toi da s
        int s = upper_bound(P.begin(), P.end(), n_k) - P.begin() - 1;
        if (s == 0) {
            cout << "0 0\n";
            continue;
        }

        // 2. Binary Search cho so tien vay it nhat (v)
        // Voi so luong s, v co the nam trong doan [t[0], t[m-1]]
        // Can tim v lon nhat sao cho co the chon duoc s sinh vien
        // Tong tien <= n_k va moi nguoi deu nhan duoc it nhat v

        ll low = 1, high = t[m-1];
        ll best_v = 0;

        while(low <= high) {
            ll mid = low + (high - low) / 2;

            // Kiem tra tinh hop le cua mid
            // Ta can chon s sinh vien sao cho tong <= n_k va moi nguoi >= mid
            // De tong nho nhat, ta nen chon cac sinh vien co tien >= mid ma co tien nho nhat co the
            // Loc ra cac sinh vien co tien >= mid
            // Neu so luong khong du, mid qua lon
            // Tinh toan tong nho nhat co the voi dieu kien nay

            // Cach 2a: Duyet bang con tro
            // Tim vi tri dau tien cua sinh vien co tien >= mid
            int idx = lower_bound(t.begin(), t.end(), mid) - t.begin();
            int cnt = m - idx;

            if (cnt < s) {
                high = mid - 1;
                continue;
            }

            // Tinh tong cua s sinh vien tu idx den idx + s - 1
            // Neu tong > n_k, thi mid qua lon
            if (P[idx + s] - P[idx] <= n_k) {
                best_v = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        cout << s << " " << best_v << "\n";
    }
}
  • Time Complexity: O(m log m + Q log m log(max_t))
  • Space Complexity: O(m)

Phương pháp này cũng dựa trên việc trước tiên tìm số lượng sinh viên tối đa ~s~. Sau đó, ta cần tìm giá trị lớn nhất của ~v~ (số tiền vay ít nhất) sao cho tồn tại một tập hợp ~s~ sinh viên thỏa mãn điều kiện. Ta có thể sử dụng Binary Search trên giá trị ~v~. Với mỗi giá trị ~v~ giả định (mid), ta kiểm tra xem có thể chọn được ~s~ sinh viên sao cho ai cũng nhận được ít nhất ~mid~ và tổng tiền ≤ ~n_k~ không. Cách kiểm tra (check(mid)):

  1. Lọc ra các sinh viên có ~t_i >= mid~.
  2. Nếu số lượng sinh viên này < ~s~, không thể thỏa mãn.
  3. Chọn ~s~ sinh viên đầu tiên trong danh sách đã lọc (những người có ~t_i~ nhỏ nhất nhưng vẫn ≥ ~mid~). Nếu tổng của họ ≤ ~n_k~, thì ~mid~ hợp lệ.

Binary Search tìm giá trị ~mid~ hợp lệ lớn nhất.

Cách Optimized Sliding Window (Two Pointers)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

void solve() {
    int m, Q;
    cin >> m >> Q;
    vector<ll> t(m);
    for (int i = 0; i < m; ++i) cin >> t[i];
    sort(t.begin(), t.end());

    vector<ll> P(m + 1, 0);
    for (int i = 0; i < m; ++i) P[i + 1] = P[i] + t[i];

    while (Q--) {
        ll n_k;
        cin >> n_k;

        // 1. Tim so luong toi da s
        int s = upper_bound(P.begin(), P.end(), n_k) - P.begin() - 1;
        if (s == 0) {
            cout << "0 0\n";
            continue;
        }

        // 2. Sliding Window
        ll current_sum = P[s];
        int r = s;

        while (r + 1 <= m && current_sum + t[r] - t[r - s] <= n_k) {
            current_sum = current_sum + t[r] - t[r - s];
            r++;
        }

        cout << s << " " << t[r - s] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}
  • Time Complexity: O(m log m + Q log m)
  • Space Complexity: O(m)

Đây là phiên bản chi tiết của Approach 1. Logic:

  • Sau khi có ~s~, ta cần tìm đoạn liên tiếp độ dài ~s~ trong mảng đã sắp xếp sao cho tổng ≤ ~n_k~ và giá trị phần tử đầu tiên của đoạn là lớn nhất.
  • Ban đầu, đoạn là [0, s-1] (tức là ~t[0]~ đến ~t[s-1]~).
  • Ta thử kéo dài đoạn sang phải: Thêm ~t[r]~ vào cuối, loại ~t[r-s]~ khỏi đầu. Nếu tổng mới ≤ ~n_k~, ta chấp nhận.
  • Vì mảng đã sắp xếp, việc này đảm bảo ta luôn xét các đoạn có tổng ≤ ~n_k~ và giá trị đầu tiên (min) tăng dần.
  • Khi không thể kéo dài thêm, đoạn hiện tại cho ta giá trị ~t[r-s]~ lớn nhất có thể.

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

Cách tiếp cận Time Space Tên
1 O(m log m + Q log m + m) ~ O(m log m + Q log m) O(m) Tham lam với Sliding Window (Two Pointers)
2 O(m log m + Q log m log(max_t)) O(m) Binary Search trên số tiền nhỏ nhất (v)
3 O(m log m + Q log m) O(m) Optimized Sliding Window (Two Pointers)

Bài học kinh nghiệm

  • Để tối đa hóa số lượng sinh viên, luôn ưu tiên chọn những người có nhu cầu vay nhỏ nhất. Sắp xếp mảng t là bước bắt buộc.
  • Sau khi xác định được số lượng sinh viên tối đa ~s~, bài toán trở thành tìm một tập hợp ~s~ phần tử liên tiếp trong mảng đã sắp xếp sao cho tổng ≤ ~n~ và phần tử đầu tiên là lớn nhất.
  • Sử dụng Sliding Window (Two Pointers) để tối ưu hóa việc tìm tập hợp ~s~ phần tử thỏa mãn điều kiện tổng tiền.

Lỗi thường gặp

  • Quên sắp xếp mảng t trước khi xử lý.
  • Sử dụng biến kiểu int cho tổng tiền (có thể lên tới 10^18), cần dùng long long.
  • Sai logic khi tìm số lượng sinh viên tối đa ~s~: cần dùng upper_bound hoặc duyệt thủ công, đảm bảo ~s~ là số lượng lớn nhất sao cho ~t[0] + ... + t[s-1] <= n~.
  • Lầm tưởng rằng chỉ cần chọn ~s~ sinh viên đầu tiên sau khi sắp xếp là đủ (ví dụ sample 2, nếu chỉ chọn 3 người đầu tiên sẽ得到 v=1, nhưng tối ưu là v=2).

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.