Hướng dẫn giải của LIST14: Tổng lớn nhất của 3 số bất kì và vị trí
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 tổng lớn nhất của ba phần tử khác vị trí trong dãy, và in vị trí của chúng theo thứ tự tăng dần. Khi có nhiều bộ cùng tổng thì lấy bộ có chỉ số nhỏ nhất theo thứ tự từ điển.
Sub 1: Vét cạn ba vòng lặp — ~O(n^3)~, dùng khi ~n \le 300~
Duyệt mọi bộ ~i < j < k~ theo thứ tự từ điển. Chỉ cập nhật khi tổng lớn hơn hẳn nên bộ được giữ là bộ đầu tiên đạt tổng lớn nhất.
Nếu chỉ nộp sub này: đúng 9/20 test.
Sub 2: Sắp xếp và chọn tham lam — ~O(n \log n)~, dùng khi mọi trường hợp còn lại
Tổng lớn nhất là tổng ba giá trị lớn nhất ~w_1 + w_2 + w_3~. Mọi bộ đạt tổng này phải có đúng ba giá trị ~\{w_1, w_2, w_3\}~. Ta chọn tham lam: chọn vị trí nhỏ nhất có giá trị cần thiết sao cho các giá trị còn lại vẫn tìm được ở sau vị trí đó (kiểm tra bằng mảng đếm hậu tố). Làm như vậy ba lần ta được bộ chỉ số nhỏ nhất theo thứ tự từ điển.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Đề không chia subtask. Sub 1 dùng cho ~n \le 300~ để kiểm tra trực tiếp, sub 2 là lời giải đầy đủ.
Chương trình đọc ~n~ và dãy. Nếu ~n \le 300~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a; // a[0..n-1]: day so (chi so bat dau tu 0)
long long bestSum;
int bi, bj, bk; // chi so (0-based) cua bo 3 so tot nhat
// Sub 1: vet can, thu moi bo ba chi so i < j < k. Dung khi n <= 300
void sub1() {
bestSum = 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++) {
long long s = a[i] + a[j] + a[k];
if (s > bestSum) { // chi cap nhat khi thuc su lon hon -> giu bo (i,j,k) nho nhat
bestSum = s;
bi = i; bj = j; bk = k;
}
}
cout << bestSum << "\n" << bi + 1 << " " << bj + 1 << " " << bk + 1 << "\n";
}
// Sub 2: tong lon nhat la tong ba so lon nhat w1 + w2 + w3. Moi bo toi uu co dung dung
// cac gia tri {w1, w2, w3}. Chon tham lam theo chi so tang dan de duoc bo (i,j,k) nho nhat.
void sub2() {
vector<long long> w = a;
sort(w.begin(), w.end(), greater<long long>());
bestSum = w[0] + w[1] + w[2];
map<long long, int> need; // can chon bao nhieu so cho moi gia tri
need[w[0]]++; need[w[1]]++; need[w[2]]++;
// suf[v][i] = so vi tri tu i den n-1 co gia tri v
map<long long, vector<int>> suf;
for (map<long long, int>::iterator it = need.begin(); it != need.end(); ++it)
suf[it->first].assign(n + 1, 0);
for (int i = n - 1; i >= 0; i--)
for (map<long long, vector<int>>::iterator it = suf.begin(); it != suf.end(); ++it)
it->second[i] = it->second[i + 1] + (a[i] == it->first ? 1 : 0);
vector<int> pick;
int pos = 0;
for (int round = 0; round < 3; round++) {
for (int i = pos; i < n; i++) {
map<long long, int>::iterator nd = need.find(a[i]);
if (nd == need.end() || nd->second == 0) continue;
nd->second--;
bool ok = true; // phan con lai co du so o sau vi tri i khong?
for (map<long long, int>::iterator it = need.begin(); it != need.end(); ++it)
if (it->second > suf[it->first][i + 1]) { ok = false; break; }
if (ok) {
pick.push_back(i);
pos = i + 1;
break;
}
nd->second++;
}
}
cout << bestSum << "\n";
for (int t = 0; t < 3; t++) cout << pick[t] + 1 << (t < 2 ? " " : "\n");
}
int main() {
cin >> n;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 300) sub1();
else sub2();
return 0;
}
Bình luận