Hướng dẫn giải của [VT Thiếu nhi] BÀI 22: GOIQUA


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 quyển sách và m quyển vở, cần ghép mỗi gói gồm một sách và một vở sao cho tổng giá không vượt K. Mỗi món chỉ dùng một lần, tìm số gói nhiều nhất.

Ý chính: nếu có t gói thì có thể chọn t quyển sách rẻ nhất và t quyển vở rẻ nhất. Ghép sách rẻ nhất với vở đắt nhất trong nhóm (ghép đối nghịch sau khi sắp xếp tăng dần) là cách ghép tốt nhất cho t gói đó. Vì vậy có thể kiểm tra từng t bằng O(t) phép so sánh, và tính chất "t gói khả thi" là đơn điệu.

Sub 1: Tăng dần số gói — ~O(n^2)~, dùng khi n, m \le 2000

Thử t = 1, 2, ... cho đến khi không ghép được t gói nữa. Đề không có test nào để chấm, sub 1 chưa được kiểm tra bằng test chấm. Chương trình đã được thử với ví dụ trong đề (kết quả 4, đúng).

Sub 2 (đầy đủ): Tìm nhị phân số gói — ~O(n \log n)~

Sắp xếp hai dãy, tìm nhị phân số gói t lớn nhất thỏa điều kiện trên. Bẫy: tổng giá có thể tới 2 \cdot 10^6, nhưng dùng long long cho chắc.

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

Hàm main đọc n, m, K và hai dãy, sắp xếp. Nếu n, m \le 2000 gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.

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

int n, m;
long long K;
vector<long long> a, b;   // a: gia sach, b: gia vo; da sap xep tang dan

// Kiem tra co goi duoc t goi qua hay khong.
// Chon t quyen sach re nhat va t quyen vo re nhat; ghep quyen sach re nhat voi vo dat nhat (a tang, b giam).
// Ghep nhu vay la cach tot nhat: neu t goi kha thi thi cach nay cung kha thi.
bool feasible(int t) {
    for (int i = 0; i < t; i++)
        if (a[i] + b[t - 1 - i] > K) return false;
    return true;
}

// Sub 1: vet can - thu t = 1, 2, ... cho den khi khong ghep duoc nua. Dung khi n, m <= 2000.
void sub1() {
    int t = 0;
    while (t < min(n, m) && feasible(t + 1)) t++;
    cout << t << "\n";
}

// Sub 2: day du O(n log n) - tim nhi phan so goi t lon nhat, moi lan kiem tra O(t).
void sub2() {
    int lo = 0, hi = min(n, m);
    while (lo < hi) {
        int mid = (lo + hi + 1) / 2;
        if (feasible(mid)) lo = mid;
        else hi = mid - 1;
    }
    cout << lo << "\n";
}

int main() {
    freopen("GOIQUA.INP", "r", stdin);
    freopen("GOIQUA.OUT", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m >> K;
    a.resize(n);
    b.resize(m);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    if (n <= 2000 && m <= 2000) sub1();   // du lieu nho: tang dan so goi
    else sub2();
    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.