Hướng dẫn giải của [200 đề thầy Đức] Bài 114: Mua rau rẻ nhất
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
Bài chỉ cần tìm quầy có giá rẻ nhất cho 1 kg, rồi nhân với số kg cần mua. Có thể mua kg lẻ nên đáp án là số thực.
Bài này chỉ có một công thức đơn giản (không có cách vét cạn nào khác đáng viết thêm), nên chỉ có 1 sub.
Sub 1: Duyệt các quầy, lấy giá nhỏ nhất — ~O(N)~
Giá của quầy ~i~ là ~a_i / b_i~ (berllar cho 1 kg). Duyệt tất cả quầy, lấy giá nhỏ nhất best, sau đó chi phí phải trả là best * M. Đạt 42/42 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long m;
cin >> n >> m;
// Giá rẻ nhất tính theo 1 kg: a/b nhỏ nhất
double best = 1e18;
for (int i = 0; i < n; i++) {
long long a, b;
cin >> a >> b;
best = min(best, (double)a / b);
}
// Mua m kg với giá rẻ nhất
cout << fixed << setprecision(8) << best * m << "\n";
return 0;
}
Bình luận