Hướng dẫn giải của [200 đề thầy Đức] Bài 84: Bánh mì kẹp
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.
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
Mỗi chiếc bánh cần 2 lát bánh mì, nên với b lát có tối đa ~\lfloor b/2 \rfloor~ chiếc. Cần chọn số bánh thịt bò x (x \le p) và số bánh thịt gà y (y \le f) sao cho x + y \le b/2 và lợi nhuận h \cdot x + c \cdot y là lớn nhất.
Sub 1: Vét cạn — ~O(p \times f)~
Thử mọi cặp (x, y) với 0 \le x \le p, 0 \le y \le f. Nếu 2x + 2y \le b thì cập nhật lợi nhuận lớn nhất. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
long long b, p, f, h, c;
cin >> b >> p >> f >> h >> c;
long long best = 0;
// Vét cạn: thử mọi số bánh kẹp thịt bò x và thịt gà y
for (long long x = 0; x <= p; x++)
for (long long y = 0; y <= f; y++)
if (2 * x + 2 * y <= b) // mỗi chiếc cần 2 lát bánh mì
best = max(best, h * x + c * y);
cout << best << "\n";
}
return 0;
}
Sub 2: Cố định số bánh bò — ~O(p)~
Với mỗi x, số bánh thịt gà tối đa là y = \min(f, b/2 - x) vì giá c dương nên làm càng nhiều càng tốt. Chỉ cần duyệt x. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
long long b, p, f, h, c;
cin >> b >> p >> f >> h >> c;
long long pairs = b / 2; // tổng số chiếc bánh tối đa theo lát bánh mì
long long best = 0;
// Cố định số bánh thịt bò x, phần còn lại làm bánh thịt gà
for (long long x = 0; x <= min(p, pairs); x++) {
long long y = min(f, pairs - x);
best = max(best, h * x + c * y);
}
cout << best << "\n";
}
return 0;
}
Sub 3: Tham lam — ~O(1)~
Loại có giá cao hơn làm trước (nhiều nhất có thể), phần lát bánh còn lại dành cho loại kia. Đây là lời giải đầy đủ, đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
long long b, p, f, h, c;
cin >> b >> p >> f >> h >> c;
long long pairs = b / 2; // số chiếc bánh tối đa làm được theo lát bánh mì
long long x, y;
// Chọn loại có giá cao hơn làm trước (tham lam), phần còn lại làm loại kia
if (h >= c) {
x = min(p, pairs);
y = min(f, pairs - x);
} else {
y = min(f, pairs);
x = min(p, pairs - y);
}
cout << h * x + c * y << "\n";
}
return 0;
}
Bình luận