Hướng dẫn giải của Chọn quà (đề HSG 12 Phú Thọ 2024-2025)
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
Cần tìm đoạn liên tiếp dài nhất có tổng nhỏ hơn $s$. Vì mọi $a_i \ge 1$ nên tổng của đoạn tăng khi mở rộng, và đó là chìa khóa để làm nhanh.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Thử mọi đoạn liên tiếp $[l, r]$, cộng dồn tổng và cập nhật độ dài lớn nhất khi tổng nhỏ hơn $s$.
Nếu chỉ nộp sub này: đúng 10/20 test (10 test lớn quá giờ).
Sub 2: Hai con trỏ (cửa sổ trượt) — ~O(n)~
Duyệt $r$ tăng dần, thêm $ar$ vào tổng. Trong khi tổng $\ge s$ thì bỏ $al$ ở bên trái và tăng $l$. Sau đó cập nhật $r - l + 1$. Bẫy: dùng long long cho tổng vì tổng có thể lên tới $10^{15}$.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu từ file CAU3.INP, ghi ra CAU3.OUT. Nếu $n \le 1000$ thì gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long s;
vector<long long> a; // a[1..n], a_i >= 1
// Sub 1: vet can O(n^2), dung khi n <= 1000.
// Thu moi doan lien tiep [l, r], tinh tong truc tiep va lay doan dai nhat co tong < s.
void sub1() {
int best = 0;
for (int l = 1; l <= n; l++) {
long long sum = 0;
for (int r = l; r <= n; r++) {
sum += a[r];
if (sum < s) best = max(best, r - l + 1);
}
}
cout << best << "\n";
}
// Sub 2: hai con tro O(n) (cua so truot), dung cho moi n.
// Vi a_i >= 1 nen khi tong >= s thi bo dan phan tu ben trai cho den khi tong < s.
void sub2() {
long long sum = 0;
int best = 0, l = 1;
for (int r = 1; r <= n; r++) {
sum += a[r];
while (l <= r && sum >= s) {
sum -= a[l];
l++;
}
best = max(best, r - l + 1);
}
cout << best << "\n";
}
int main() {
freopen("CAU3.INP", "r", stdin);
freopen("CAU3.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> s;
a.assign(n + 1, 0);
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận