Hướng dẫn giải của LIST13: Tổng lớn nhất của 3 số bất kì
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 n số nguyên, tìm tổng lớn nhất của ba số bất kì trong dãy. Ba số lớn nhất của dãy luôn cho tổng lớn nhất, nên chỉ cần tìm được ba số đó.
Sub 1: Vét cạn — ~O(n^3)~
Thử mọi bộ ba vị trí i < j < k, cộng ba số rồi lấy giá trị lớn nhất. Cách này đúng nhưng với n lên đến 10^5 thì số bộ ba quá lớn nên chạy quá giờ.
Kết quả chấm: đạt 9/20 test (SUB ok 9/20, TLE 11, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Vét cạn: thử mọi bộ ba chỉ số i < j < k
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";
return 0;
}
Sub 2: Duyệt một lần, giữ 3 số lớn nhất — ~O(n)~
Duyệt dãy một lần và giữ ba biến t1 ≥ t2 ≥ t3 là ba số lớn nhất đã gặp. Khi gặp số x mới, chèn x vào đúng vị trí và đẩy các số nhỏ hơn xuống. Đáp án là t1 + t2 + t3. Lưu ý: tổng có thể lên tới 3·10^6 nên dùng kiểu long long cho an toàn.
Kết quả chấm: đạt 20/20 test
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
// t1 >= t2 >= t3 là 3 số lớn nhất đã gặp
long long t1 = LLONG_MIN, t2 = LLONG_MIN, t3 = LLONG_MIN;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
if (x > t1) {
t3 = t2; t2 = t1; t1 = x;
} else if (x > t2) {
t3 = t2; t2 = x;
} else if (x > t3) {
t3 = x;
}
}
// Tổng 3 số lớn nhất là đáp án (n >= 3)
cout << t1 + t2 + t3 << "\n";
return 0;
}
Bình luận