Hướng dẫn giải của [Beginner Free Contest 01] KSUM
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 n viên kẹo có độ ngon w_i (n <= 10^5). Chọn k viên kẹo liên tiếp (1 <= k <= n) sao cho tổng độ ngon lớn nhất, in tổng đó.
Sub 1: Thử mọi đoạn k viên — ~O(n*k)~
Với mỗi vị trí bắt đầu, cộng trực tiếp k viên kẹo rồi lấy max. Đúng nhưng với n = 10^5 thì 30 test bị TLE.
Kết quả chấm: đạt 20/50 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> w(n);
for (auto &x : w) cin >> x;
long long best = LLONG_MIN;
// Vet can: voi moi vi tri bat dau, cong truc tiep k vien keo
for (int i = 0; i + k <= n; i++) {
long long s = 0;
for (int j = i; j < i + k; j++) s += w[j];
best = max(best, s);
}
cout << best << endl;
return 0;
}
Sub 2: Cửa sổ trượt — ~O(n)~
Tính tổng k viên đầu tiên. Mỗi bước thêm viên mới và bỏ viên cũ: s = s + w[i] - w[i-k]. Tổng có thể đến 10^5 * 10^9 = 10^14 nên dùng long long.
Kết quả chấm: đạt 50/50 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
vector<long long> w(n);
for (auto &x : w) cin >> x;
// Cua so truot: tong cua k vien dau, sau do bo vien dau va them vien ke tiep
long long s = 0;
for (int i = 0; i < k; i++) s += w[i];
long long best = s;
for (int i = k; i < n; i++) {
s += w[i] - w[i - k];
best = max(best, s);
}
cout << best << endl;
return 0;
}
Bình luận