Hướng dẫn giải của [200 đề thầy Đức] Bài 165: Dãy con liên tiếp các số âm có tổng nhỏ nhất
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 con liên tiếp chỉ gồm các số âm sao cho tổng nhỏ nhất. Nếu dãy không có số âm nào thì in 0. Tổng có thể lên tới 10^5 × 10^6 = 10^11, nên cần dùng kiểu long long.
Sub 1: Vét cạn — ~O(N^2)~
Với mỗi vị trí i có A[i] < 0, mở rộng đoạn sang phải j = i, i+1, … khi các số vẫn còn âm, cộng dồn tổng và cập nhật tổng nhỏ nhất. Đạt 17/21 test, 4 test còn lại quá giờ vì dãy dài N = 10^5 có thể có tới O(N^2) đoạn.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
bool found = false;
long long best = 0;
// Vét cạn: xuất phát từ mỗi i, mở rộng j khi a[j] còn âm
for (int i = 0; i < n; i++) {
if (a[i] >= 0) continue;
long long s = 0;
for (int j = i; j < n && a[j] < 0; j++) {
s += a[j];
if (!found || s < best) {
best = s;
found = true;
}
}
}
cout << (found ? best : 0) << "\n";
}
return 0;
}
Sub 2: Duyệt một lần theo đoạn âm liên tiếp — ~O(N)~
Nhận xét: trong một đoạn số âm liên tiếp (đoạn tối đại), mọi đoạn con đều có tổng âm, và việc thêm một số âm vào đoạn chỉ làm tổng giảm. Vì vậy đoạn con có tổng nhỏ nhất trong đoạn tối đại đó chính là cả đoạn. Do đó ta chỉ cần duyệt một lần, cộng dồn tổng của từng đoạn âm, và khi gặp số không âm hoặc hết dãy thì so sánh với tổng nhỏ nhất hiện có.
Bẫy cần chú ý: đoạn âm có thể nằm ở cuối dãy nên phải xử lý sau vòng lặp; nếu không có đoạn âm nào thì in 0. Dùng long long cho tổng. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
bool found = false; // đã gặp ít nhất một đoạn số âm chưa
long long best = 0; // tổng nhỏ nhất tìm được
long long run = 0; // tổng đoạn số âm đang xét
bool inRun = false; // đang ở trong một đoạn số âm?
for (int i = 0; i < n; i++) {
if (a[i] < 0) {
run += a[i];
inRun = true;
} else if (inRun) {
// kết thúc đoạn âm: cập nhật min
if (!found || run < best) best = run;
found = true;
run = 0;
inRun = false;
}
}
if (inRun) { // đoạn âm kết thúc ở cuối dãy
if (!found || run < best) best = run;
found = true;
}
cout << (found ? best : 0) << "\n";
}
return 0;
}
Bình luận