Hướng dẫn giải của [200 đề thầy Đức] Bài 175: Bộ ba có tích lớn 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
Cho dãy n số nguyên (3 ≤ n ≤ 100, |a_i| ≤ 1000), tìm tích lớn nhất của ba số trong dãy. Chú ý dãy có thể toàn số âm, khi đó tích lớn nhất là tích của ba số có giá trị tuyệt đối nhỏ nhất (tích âm lớn nhất vẫn có thể là đáp án).
Sub 1: Vét cạn — ~O(N^3)~
Thử mọi bộ ba chỉ số i < j < k, tính tích rồi lấy giá trị lớn nhất. Với N ≤ 100 cách này chạy trong khoảng 10^6 phép tính nên đạt 24/24 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Vét cạn: thử mọi bộ ba chỉ số i < j < k
long long best = LLONG_MIN;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
best = max(best, a[i] * a[j] * a[k]);
cout << best << "\n";
return 0;
}
Sub 2: Sắp xếp rồi xét hai trường hợp — ~O(N log N)~
Sắp xếp dãy tăng dần. Tích lớn nhất của ba số chỉ có thể là một trong hai dạng:
- Ba số lớn nhất:
a[n-1] × a[n-2] × a[n-3]. - Hai số âm nhỏ nhất (tích của chúng dương) nhân với số lớn nhất:
a[0] × a[1] × a[n-1].
Lấy giá trị lớn hơn trong hai dạng. Dùng long long vì tích ba số có thể lên tới 10^9. Đạt 24/24 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
// Tích lớn nhất là một trong hai trường hợp:
// 1) ba số lớn nhất: a[n-1] * a[n-2] * a[n-3]
// 2) hai số âm nhỏ nhất (tích dương) nhân số lớn nhất: a[0] * a[1] * a[n-1]
long long c1 = a[n - 1] * a[n - 2] * a[n - 3];
long long c2 = a[0] * a[1] * a[n - 1];
cout << max(c1, c2) << "\n";
return 0;
}
Bình luận