Hướng dẫn giải của C2
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 có tổng lớn hơn hoặc bằng ~K~ và số phần tử ít nhất. Các số đều dương nên tổng tăng khi mở rộng đoạn.
Sub 1: vét cạn — ~O(n^2)~, dùng khi ~n \le 5000~
Với mỗi điểm bắt đầu, cộng dần đến khi tổng đủ ~K~ thì dừng. Nếu chỉ nộp sub này: đúng 16/20 test.
Sub 2: hai con trỏ — ~O(n)~
Mở rộng đoạn bên phải, thu hẹp bên trái khi vẫn còn đủ ~K~. Đúng 20/20 test. Tổng có thể lên tới ~10^{15}~, dùng long long.
Chương trình hoàn chỉnh
main đọc n, K và dãy số. Nếu ~n \le 5000~ thì gọi sub1, ngược lại gọi sub2. Nếu không có đoạn nào thì in 0.
#include <bits/stdc++.h>
using namespace std;
int n;
long long K;
vector<long long> a;
// Sub 1: vét cạn mọi đoạn bắt đầu tại i, cộng dần đến khi đủ K. O(n^2)
// Dùng khi n <= 5000.
void sub1() {
int best = 0;
for (int i = 0; i < n; i++) {
long long s = 0;
for (int j = i; j < n; j++) {
s += a[j];
if (s >= K) {
int len = j - i + 1;
if (best == 0 || len < best) best = len;
break; // các đoạn dài hơn từ i không cần xét nữa
}
}
}
cout << best << "\n";
}
// Sub 2: hai con trỏ (các số đều dương nên tổng tăng khi mở rộng). O(n).
void sub2() {
int best = 0;
long long s = 0;
int l = 0;
for (int r = 0; r < n; r++) {
s += a[r];
while (l <= r && s - a[l] >= K) { // bớt phần đầu nếu vẫn đủ K
s -= a[l];
l++;
}
if (s >= K) {
int len = r - l + 1;
if (best == 0 || len < best) best = len;
}
}
cout << best << "\n";
}
int main() {
freopen("CAU2.INP", "r", stdin);
freopen("CAU2.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> K;
a.resize(n);
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 5000) sub1();
else sub2();
return 0;
}
Bình luận