Hướng dẫn giải của [SUMOFNEG] Tổng âm
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
Tìm đoạn liên tiếp dài nhất có tổng âm. Gọi $Pk = a1 + \dots + ak$ (với $P0 = 0$). Đoạn $a{i+1} \dots aj$ có tổng âm khi $Pj < Pi$, và độ dài là $j - i$.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 2000~
Thử mọi cặp $i < j$, kiểm tra $Pj < Pi$ và cập nhật $j - i$ lớn nhất.
Nếu chỉ nộp sub này: đúng 12/14 test (2 test lớn quá giờ).
Sub 2: Chỉ xét các mốc đáng chú ý — ~O(n \log n)~
Có thể bỏ qua nhiều cặp:
- Với $i$: chỉ cần xét các $i$ mà $Pi$ lớn hơn mọi $Pk$ với $k < i$. Nếu có $k < i$ mà $Pk \ge Pi$ thì $k$ cho đoạn dài hơn và vẫn thỏa điều kiện.
- Với $j$: chỉ cần xét các $j$ mà $Pj$ nhỏ hơn mọi $Pk$ với $k > j$. Nếu có $k > j$ mà $Pk \le Pj$ thì $k$ đẹp hơn.
Các $j$ như vậy có $Pj$ tăng dần theo chỉ số, nên với mỗi $i$ dùng lower_bound để tìm $j$ lớn nhất có $Pj < P_i$. Bẫy: $j$ phải lớn hơn $i$.
Nếu chỉ nộp sub này: đúng 14/14 test.
Chương trình hoàn chỉnh
main đọc dữ liệu từ file SUMOFNEG.INP, ghi ra SUMOFNEG.OUT. Nếu $n \le 2000$ thì gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a; // a[1..n]
vector<long long> P; // P[0..n], P[k] = a_1 + ... + a_k
// Sub 1: vet can O(n^2), dung khi n <= 2000.
// Moi doan a_{i+1..j} tuong ung cap (i, j) voi i < j, tong = P[j] - P[i].
void sub1() {
int best = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j <= n; j++)
if (P[j] - P[i] < 0) best = max(best, j - i);
cout << best << "\n";
}
// Sub 2: O(n log n), dung cho moi n.
// Chi can xet i la moc "ky luc" ben trai (P_i lon hon moi P_k voi k < i)
// va j la moc "ky luc" ben phai (P_j nho hon moi P_k voi k > j).
// Khi do voi moi i tim j lon nhat co P_j < P_i bang nhi phan tren day j.
void sub2() {
// Ben trai: i co P_i > max cua cac P_k truoc do (k < i)
vector<int> L;
long long mx = LLONG_MIN;
for (int i = 0; i < n; i++)
if (P[i] > mx) {
L.push_back(i);
mx = P[i];
}
// Ben phai: j co P_j < min cua cac P_k sau do (k > j); duyet tu phai sang
vector<int> R;
long long mn = LLONG_MAX;
for (int j = n; j >= 1; j--)
if (P[j] < mn) {
R.push_back(j);
mn = P[j];
}
reverse(R.begin(), R.end()); // chi so tang dan; P tren R cung tang dan
vector<long long> vals;
for (int j : R) vals.push_back(P[j]);
int best = 0;
for (int i : L) {
// cac j trong R co P_j < P_i la mot tien to cua R
int cnt = lower_bound(vals.begin(), vals.end(), P[i]) - vals.begin();
if (cnt == 0) continue;
int j = R[cnt - 1]; // j lon nhat thoa P_j < P_i
if (j > i) best = max(best, j - i);
}
cout << best << "\n";
}
int main() {
freopen("SUMOFNEG.INP", "r", stdin);
freopen("SUMOFNEG.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.assign(n + 1, 0);
P.assign(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
P[i] = P[i - 1] + a[i];
}
if (n <= 2000) sub1();
else sub2();
return 0;
}
Bình luận