Hướng dẫn giải của [VT Thiếu nhi] BÀI 20: Tarr1
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 A gồm n số và số X. Tìm S = A[i] · X lớn nhất có thể.
Sub 1: Vét cạn — ~O(n)~
Thử từng phần tử A[i], tính A[i] · X rồi lấy giá trị lớn nhất. Dùng long long vì tích có thể vượt 2·10^9. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("Tarr1.INP", "r", stdin);
freopen("Tarr1.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long x;
cin >> n >> x;
// Vét cạn: thử từng phần tử A[i], tính S = A[i] * X rồi lấy giá trị lớn nhất
long long best = LLONG_MIN;
for (int i = 0; i < n; i++) {
long long a;
cin >> a;
best = max(best, a * x);
}
cout << best << '\n';
return 0;
}
Sub 2: Chọn phần tử cực trị — ~O(n)~
Với X ≥ 0, tích lớn nhất khi A[i] lớn nhất; với X < 0, tích lớn nhất khi A[i] nhỏ nhất. Vì vậy chỉ cần tìm giá trị max và min của dãy, rồi nhân với X đúng một lần. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("Tarr1.INP", "r", stdin);
freopen("Tarr1.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
long long x;
cin >> n >> x;
long long mx = LLONG_MIN, mn = LLONG_MAX;
for (int i = 0; i < n; i++) {
long long a;
cin >> a;
mx = max(mx, a);
mn = min(mn, a);
}
// Nếu X >= 0, S lớn nhất khi A[i] lớn nhất; nếu X < 0, S lớn nhất khi A[i] nhỏ nhất
long long ans = (x >= 0) ? mx * x : mn * x;
cout << ans << '\n';
return 0;
}
Bình luận