Hướng dẫn giải của [VTT Q4 Contest 07] Bài 3: Máy nhiệt năng [MAXENERGY]
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
Chọn ba chỉ số ~i < j < k~ để tối đa hóa ~(t_i - t_j)(t_j - t_k)~. Mấu chốt: khi cố định ~j~, hai thừa số được chọn độc lập (một bên chọn ~i~, một bên chọn ~k~).
Sub 1: Vét cạn — ~O(n^3)~, dùng khi ~n \le 100~
Thử mọi bộ ba ~(i, j, k)~ và lấy giá trị lớn nhất. Nếu chỉ nộp sub này: đúng 10/20 test.
Sub 2: Cố định ~j~ — ~O(n^2)~, dùng khi ~n \le 5000~
Với mỗi ~j~, thừa số ~t_i - t_j~ nhận giá trị trong khoảng từ ~\min - t_j~ đến ~\max - t_j~ (min, max của các ~t_i~ bên trái), thừa số ~t_j - t_k~ tương tự theo các ~t_k~ bên phải. Tích hai đại lượng bậc nhất là hàm song tuyến tính nên lớn nhất tại các đầu mút: thử 4 tổ hợp (min/max bên trái) nhân (min/max bên phải). Chú ý đáp án có thể âm (ví dụ dãy tăng dần không cho hai thừa số cùng dấu), nên khởi tạo kết quả bằng giá trị rất nhỏ, không phải 0. Nếu chỉ nộp sub này: đúng 16/20 test.
Sub 3: Tiền tố và hậu tố — ~O(n)~
Tính sẵn max/min của tiền tố ~t_1..t_{j-1}~ và hậu tố ~t_{j+1}..t_n~, rồi dùng đúng 4 tổ hợp như trên cho mỗi ~j~. Tích tối đa ~(2 \cdot 10^6)^2 = 4 \cdot 10^{12}~ 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 \le 100~ gọi sub1, ~n \le 5000~ gọi sub2, còn lại gọi sub3. 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 t[1000005];
long long pmx[1000005], pmn[1000005], smx[1000005], smn[1000005];
// Sub 1: vét cạn ba chỉ số i<j<k — O(n^3)
void sub1() {
long long best = LLONG_MIN;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
for (int k = j + 1; k <= n; k++)
best = max(best, (t[i] - t[j]) * (t[j] - t[k]));
cout << best << "\n";
}
// Sub 2: cố định j, quét tìm giá trị lớn nhất/nhỏ nhất bên trái và bên phải — O(n^2)
void sub2() {
long long best = LLONG_MIN;
for (int j = 2; j < n; j++) {
long long mxL = LLONG_MIN, mnL = LLONG_MAX, mxR = LLONG_MIN, mnR = LLONG_MAX;
for (int i = 1; i < j; i++) { mxL = max(mxL, t[i]); mnL = min(mnL, t[i]); }
for (int k = j + 1; k <= n; k++) { mxR = max(mxR, t[k]); mnR = min(mnR, t[k]); }
// x-y thuộc [mnL-t_j, mxL-t_j], y-z thuộc [t_j-mxR, t_j-mnR]; tích lớn nhất đạt ở đầu mút
long long a[2] = {mnL - t[j], mxL - t[j]};
long long b[2] = {t[j] - mxR, t[j] - mnR};
for (int u = 0; u < 2; u++)
for (int v = 0; v < 2; v++)
best = max(best, a[u] * b[v]);
}
cout << best << "\n";
}
// Sub 3: dùng mảng max/min tiền tố và hậu tố — O(n)
void sub3() {
pmx[1] = pmn[1] = t[1];
for (int i = 2; i <= n; i++) { pmx[i] = max(pmx[i - 1], t[i]); pmn[i] = min(pmn[i - 1], t[i]); }
smx[n] = smn[n] = t[n];
for (int i = n - 1; i >= 1; i--) { smx[i] = max(smx[i + 1], t[i]); smn[i] = min(smn[i + 1], t[i]); }
long long best = LLONG_MIN;
for (int j = 2; j < n; j++) {
long long a[2] = {pmn[j - 1] - t[j], pmx[j - 1] - t[j]};
long long b[2] = {t[j] - smx[j + 1], t[j] - smn[j + 1]};
for (int u = 0; u < 2; u++)
for (int v = 0; v < 2; v++)
best = max(best, a[u] * b[v]);
}
cout << best << "\n";
}
int main() {
freopen("MAXENERGY.INP", "r", stdin);
freopen("MAXENERGY.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> t[i];
if (n <= 100) sub1();
else if (n <= 5000) sub2();
else sub3();
}
Bình luận