Hướng dẫn giải của Tích lớn nhất
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, , ,
Hiểu bài toán
Bài toán yêu cầu tìm tích lớn nhất của hai trong ba số nguyên dương a, b, c cho trước. Ví dụ, với a=2, b=3, c=5, các tích cần so sánh là 23=6, 35=15, 2*5=10; tích lớn nhất là 15.
Các cách tiếp cận
Cách So sánh trực tiếp
long long a, b, c;
cin >> a >> b >> c;
long long s = a * b;
long long t = b * c;
long long k = a * c;
long long ans = max(s, max(t, k));
cout << ans;
- Time Complexity: O(1)
- Space Complexity: O(1)
Tính toán trực tiếp ba tích p1 = ab, p2 = bc, p3 = a*c và tìm giá trị lớn nhất trong ba giá trị này. Cách này đơn giản, dễ hiểu và hiệu quả về mọi mặt.
Cách Tối ưu bằng phép chia
long long a, b, c;
cin >> a >> b >> c;
long long ans = a * b * c / min({a, b, c});
cout << ans;
- Time Complexity: O(1)
- Space Complexity: O(1)
Tích lớn nhất của hai số trong ba số là tích của ba số chia cho số nhỏ nhất. Ví dụ: với 2,3,5, ta có (235)/2 = 15. Cần lưu ý đến nguy cơ tràn số nếu dùng phép nhân trước khi chia. Tuy nhiên, với dữ liệu đầu vào là số nguyên dương và nằm trong giới hạn long long, cách này thường an toàn.
Cách Tối ưu bằng cách loại trừ
long long a, b, c;
cin >> a >> b >> c;
long long min_val = min({a, b, c});
long long ans;
if (min_val == a) ans = b * c;
else if (min_val == b) ans = a * c;
else ans = a * b;
cout << ans;
- Time Complexity: O(1)
- Space Complexity: O(1)
Thay vì tính cả ba tích, ta chỉ cần loại trừ số nhỏ nhất và nhân hai số còn lại. Cách này tránh được các phép tính thừa và đảm bảo không tràn số.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(1) | O(1) | So sánh trực tiếp |
| 2 | O(1) | O(1) | Tối ưu bằng phép chia |
| 3 | O(1) | O(1) | Tối ưu bằng cách loại trừ |
Bài học kinh nghiệm
- Tích lớn nhất của hai số trong ba số là tích của hai số lớn nhất
- Có thể tính nhanh bằng cách lấy tích ba số chia cho số nhỏ nhất
Lỗi thường gặp
- Tràn số khi tính tích ba số trước khi chia
- Quên xử lý số âm (bài này yêu cầu số nguyên dương nên không gặp)
Bình luận