Hướng dẫn giải của [200 đề thầy Đức] Bài 69: Mua nước
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 mua đúng $N$ lít nước bằng chai 1 lít (giá $a$) và chai 2 lít (giá $b$), sao cho tổng tiền thấp nhất. Có tối đa $T \le 500$ bộ dữ liệu và $N \le 10^{12}$ nên không thể duyệt theo từng lít.
Sub 1: Vét cạn số chai 2 lít — ~O(N)~
Gọi $k$ là số chai 2 lít, khi đó cần $N - 2k$ chai 1 lít. Thử mọi $k$ từ $0$ đến $\lfloor N/2 \rfloor$, tính $kb + (N-2k)a$ và lấy giá nhỏ nhất. Cách này đúng với mọi test nhưng chậm khi $N$ lớn: đạt 9/21 test, 12 test quá giờ, không sai test nào.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
// Đọc hết dữ liệu trước rồi mới tính, để không làm nghẽn luồng nhập.
vector<array<long long, 3>> tests(T);
for (auto &t : tests) cin >> t[0] >> t[1] >> t[2];
for (auto &t : tests) {
long long N = t[0], a = t[1], b = t[2];
// Vét cạn: thử mọi số chai 2 lít k (từ 0 đến N/2), còn lại N - 2k lít mua bằng chai 1 lít.
long long best = LLONG_MAX;
for (long long k = 0; 2 * k <= N; k++) {
long long cost = k * b + (N - 2 * k) * a;
best = min(best, cost);
}
cout << best << "\n";
}
return 0;
}
Sub 2: Chọn loại rẻ hơn theo từng lít — ~O(1)~
So sánh giá mỗi lít: chai 1 lít là $a$, chai 2 lít là $b/2$.
- Nếu $2a \le b$: chai 2 lít không rẻ hơn, mua toàn bộ $N$ chai 1 lít với giá $N \cdot a$.
- Nếu $2a > b$: chai 2 lít rẻ hơn. Mua $\lfloor N/2 \rfloor$ chai 2 lít, và nếu $N$ lẻ thì mua thêm 1 chai 1 lít. Giá là $\lfloor N/2 \rfloor \cdot b + (N \bmod 2) \cdot a$.
Lý do đúng: nếu thay hai chai 1 lít bằng một chai 2 lít thì tiết kiệm $2a - b > 0$, nên càng ít chai 1 lít càng tốt. Ví dụ $N = 7$, $a = 3$, $b = 2$: $2a = 6 > 2$, cần $3 \cdot 2 + 1 \cdot 3 = 9$.
Bẫy cần chú ý: $N \cdot a$ có thể lên đến $10^{15}$, phải dùng long long.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
long long N, a, b;
cin >> N >> a >> b;
if (2 * a <= b) {
// Mua chai 2 lít không lợi: mua toàn bộ bằng chai 1 lít (giá mỗi lít là a).
cout << N * a << "\n";
} else {
// Chai 2 lít rẻ hơn: mua càng nhiều chai 2 lít càng tốt, phần lẻ (nếu N lẻ) mua 1 chai 1 lít.
long long k = N / 2;
long long cost = k * b + (N % 2) * a;
cout << cost << "\n";
}
}
return 0;
}
Bình luận