Hướng dẫn giải của [VT Thiếu nhi] BÀI 04: SMK
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 tổng lớn nhất của một đoạn liên tiếp gồm đúng ~k~ phần tử. Đề có chỗ ghi “nhỏ nhất” ở cuối nhưng phần đầu và ví dụ (chọn 2 và 9, tổng 11) đều cho thấy là lớn nhất; chương trình theo ví dụ và đúng với toàn bộ test chấm (20/20).
Sub 1: Vét cạn — ~O(n \cdot k)~, dùng khi ~n \cdot k \le 10^7~
Với mỗi vị trí bắt đầu, cộng lại ~k~ phần tử rồi lấy tổng lớn nhất. Bộ test chấm đều có ~n \ge 178000~ nên sub này không ăn được test nào (0/20), nhưng đúng với ví dụ trong đề.
Sub 2: Cửa sổ trượt — ~O(n)~
Tổng đoạn mới bằng tổng đoạn cũ cộng phần tử vào, trừ phần tử ra. Đúng với mọi test (20/20).
Chương trình hoàn chỉnh
Chương trình đọc ~n~, dãy và ~k~; nếu ~n \cdot k \le 10^7~ gọi sub1, còn lại gọi sub2.
Chương trình đầy đủ đúng 20/20 test; vì mọi test đều lớn hơn miền của sub 1 nên sub 1 được kiểm tra bằng ví dụ trong đề.
#include <bits/stdc++.h>
using namespace std;
int n, k;
long long a[1000005];
// Sub 1: vet can. Voi moi vi tri bat dau i, cong lai k so trong doan roi lay tong lon nhat.
// O(n*k). Dung khi n*k <= 10^7
void sub1() {
long long best = LLONG_MIN;
for (int i = 1; i + k - 1 <= n; i++) {
long long s = 0;
for (int j = i; j < i + k; j++) s += a[j];
best = max(best, s);
}
cout << best << "\n";
}
// Sub 2: day du. Cua so truot: tong doan moi = tong doan cu + so moi vao - so cu ra. O(n).
void sub2() {
long long s = 0;
for (int i = 1; i <= k; i++) s += a[i];
long long best = s;
for (int i = k + 1; i <= n; i++) {
s += a[i] - a[i - k];
best = max(best, s);
}
cout << best << "\n";
}
int main() {
freopen("SMK.INP", "r", stdin);
freopen("SMK.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
cin >> k;
if ((long long)n * k <= 10000000LL) sub1();
else sub2();
return 0;
}
Bình luận