Hướng dẫn giải của Bộ ba hoàn hảo (bản trung bình)
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.
Tác giả: Hieu Nguyen
Ý tưởng
Bài này có 3 hướng làm, tuy nhiên chỉ thuật toán có độ phức tạp O(n) mới không bị TLE.
Về cơ bản, tích 3 số lớn nhất sẽ là max của 1 trong 2 trường hợp:
- Tích của 3 số dương lớn nhất
- Tích của 2 số âm bé nhất và một số dương lớn nhất
Lưu ý: Nếu dùng C++ thì bạn nên tham khảo Tips để tránh bị TLE dù thuật toán có độ phức tạp ~O(n)~.
Thuật toán 1: Tham lam
- Độ phức tạp ~O(n^3)~
maxVal = a[0] * a[1] * a[2];
for (int i = 0; i < n; i++){
for (int j = i+1; j < n; j++){
for (int k = j+1; k < n; k++){
newVal = a[i] * a[j] * a[k];
if (newVal > maxVal){
maxVal = newVal;
}
}
}
}
cout << maxVal << "\n";
Thuật toán 2: Sắp xếp
- Độ phức tạp ~O(nlog(n))~ nếu sử dụng thuật toán sắp xếp tối ưu.
#include <iostream>
#include <algorithm>
using namespace std;
int a[100000005];
int main(){
int n;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
sort(a, a+n);
long long ans = max(a[0]*a[1]*a[n-1], a[n-1]*a[n-2]*a[n-3]);
cout << ans << endl;
}
Gợi ý lời giải
- Trong 1 vòng lặp, đồng thời tìm 3 phần tử lớn nhất và 2 phần tử bé nhất.
- Độ phức tạp: ~O(n)~
#include <iostream>
using namespace std;
int a[100000005];
int main(){
cin.sync_with_stdio(0); // fast I/O
cin.tie(0); // fast I/O
int n;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
long long max1 = -1e9, max2 = -1e9, max3 = -1e9;
long long min1 = 1e9, min2 = 1e9;
for (int i = 0; i < n; i++){
if (a[i] > max1){
max3 = max2;
max2 = max1;
max1 = a[i];
}
else if (a[i] > max2){
max3 = max2;
max2 = a[i];
}
else if (a[i] > max3){
max3 = a[i];
}
if (a[i] < min1){
min2 = min1;
min1 = a[i];
}
else if (a[i] < min2){
min2 = a[i];
}
}
long long ans = max(max1 * max2 * max3, max1 * min1 * min2);
cout << ans << endl;
}
Bình luận