Hướng dẫn giải của Tích lớn nhất (THCS KS3 VTT)
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
Tìm ba số trong dãy có tích lớn nhất. Vì các số có thể âm, tích lớn nhất là tích của ba số lớn nhất, hoặc tích của hai số nhỏ nhất (có thể âm) với số lớn nhất.
Sub 1: Vét cạn - ~O(n^3)~, dùng khi ~n \le 100~
Thử mọi bộ ba chỉ số i < j < k. Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Sắp xếp - ~O(n \log n)~
Sắp dãy rồi lấy max của ~a_n a_{n-1} a_{n-2}~ và ~a_1 a_2 a_n~. Bẫy: tích có thể lên tới ~10^{15}~ nên dùng long long. Đúng 20/20 test.
Chương trình hoàn chỉnh
Bài có file PROMAX.INP và PROMAX.OUT nên main dùng freopen đúng tên. Nếu ~n \le 100~ gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a;
// Sub 1: vet can - thu moi bo ba (i, j, k) voi i < j < k. Dung khi n <= 100.
void sub1() {
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";
}
// Sub 2: sap xep. Tich lon nhat la mot trong hai truong hop:
// 3 so lon nhat, hoac 2 so nho nhat (co the am) va so lon nhat.
void sub2() {
sort(a.begin(), a.end());
long long p1 = a[n - 1] * a[n - 2] * a[n - 3];
long long p2 = a[0] * a[1] * a[n - 1];
cout << max(p1, p2) << "\n";
}
int main() {
freopen("PROMAX.INP", "r", stdin);
freopen("PROMAX.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.resize(n);
for (auto& x : a) cin >> x;
if (n <= 100) sub1();
else sub2();
return 0;
}
Bình luận