Hướng dẫn giải của [200 đề thầy Đức] Bài 36: Đi xe bus
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
Gọi k là số vé đặc biệt mua, j là số vé thường mua. Cần k·m + j ≥ n và chi phí là k·b + j·a. Ta tìm chi phí nhỏ nhất.
Sub 1: Vét cạn số vé mỗi loại — ~O(N^2)~
Thử mọi k và j trong khoảng 0..N, kiểm tra đủ số lần đi, lấy chi phí nhỏ nhất. Đạt 19/19 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, m, a, b;
cin >> n >> m >> a >> b;
long long best = LLONG_MAX;
// Vet can: thu moi so ve dac biet k va so ve thuong j
for (long long k = 0; k <= n; k++)
for (long long j = 0; j <= n; j++)
if (k * m + j >= n) // du so lan di
best = min(best, k * b + j * a);
cout << best << "\n";
return 0;
}
Sub 2: Công thức — ~O(1)~
Gọi k = n / m và r = n % m. Chi phí tăng tuyến tính theo số vé đặc biệt, nên chỉ cần xét 3 phương án: toàn vé thường (n·a); k vé đặc biệt cộng r vé thường (k·b + r·a); và k+1 vé đặc biệt nếu r > 0 ((k+1)·b). Bẫy: vé đặc biệt chỉ đáng mua khi b rẻ hơn m·a, nhưng cả ba phương án đã được so sánh nên không cần xét thêm. Đạt 19/19 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n, m, a, b;
cin >> n >> m >> a >> b;
long long k = n / m; // so ve dac biet mua du de chay tron vong
long long r = n % m; // so lan con lai
// Chi xet 3 phuong an: toan ve thuong; k ve dac biet + r ve thuong; k+1 ve dac biet
long long best = min(n * a, k * b + r * a);
if (r > 0) best = min(best, (k + 1) * b);
cout << best << "\n";
return 0;
}
Bình luận