Hướng dẫn giải của [VT Thiếu nhi] BÀI 22: GOIQUA
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