Hướng dẫn giải của [VTT Q4 Contest 13] Bài 1: Tích lớn nhất [PROMAX]
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
Cần chọn ba phần tử của dãy sao cho tích lớn nhất. Điểm mấu chốt là dãy có thể chứa số âm: hai số âm nhân nhau cho số dương.
Sub 1: Vét cạn — ~O(n^3)~, dùng khi ~n \le 100~
Duyệt mọi bộ ba vị trí ~i < j < k~, tính tích và lấy lớn nhất. Nếu chỉ nộp sub này: đúng 10/20 test (các test lớn bị quá thời gian).
Sub 2: Sắp xếp — ~O(n \log n)~
Sau khi sắp xếp tăng dần, tích lớn nhất chỉ có thể là một trong hai ứng viên: ba số lớn nhất, hoặc hai số nhỏ nhất (có thể đều âm) nhân với số lớn nhất. Lấy max của hai tích. Tích tối đa cỡ ~10^{15}~ nên dùng long long. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu, nếu ~n \le 100~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[100005];
// Sub 1: vét cạn mọi bộ ba — O(n^3), dùng 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: sắp xếp — tích lớn nhất là 3 số lớn nhất hoặc 2 số nhỏ nhất nhân số lớn nhất
void sub2() {
sort(a, a + n);
long long x = a[n - 1] * a[n - 2] * a[n - 3];
long long y = a[0] * a[1] * a[n - 1];
cout << max(x, y) << "\n";
}
int main() {
freopen("PROMAX.INP", "r", stdin);
freopen("PROMAX.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 100) sub1();
else sub2();
}
Bình luận