Giả sử chúng ta có ba số n, a và b. Chúng ta muốn mua n lít nước. Chỉ có hai loại bình nước gần đó, bình 1 lít và bình 2 lít. Bình loại đầu tiên giá a đồng và bình loại thứ hai giá b đồng. Chúng ta muốn chi ít tiền nhất có thể. Chúng ta phải tìm số tiền tối thiểu cần để mua đúng n lít nước.
Ví dụ, nếu đầu vào là n = 7; a = 3; b = 2, thì đầu ra sẽ là 9, vì với 3 bình 2 lít ta có 6 lít nước giá 6, sau đó cần một bình 1 lít giá 3.
Các bước
Để giải quyết bài toán này, chúng ta sẽ làm theo các bước sau:
b := minimum của a * 2 và b return (n / 2 * b) + (n mod 2) * a
Ví dụ
Xem triển khai sau để hiểu rõ hơn:
#include <bits/stdc++.h> using namespace std; int solve(int n, int a, int b) { b = min(a * 2, b); return n / 2 * b + n % 2 * a; } int main() { int n = 7; int a = 3; int b = 2; cout << solve(n, a, b) << endl; }Đầu vào
7, 3, 2
Đầu ra
9