Hướng dẫn giải của [KS cụm 2 QL] Câu 2: Độ dài đoạn con
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
Tim doan con ngan nhat co tong >= K (cac A_i duong).
Sub 1: Vet can, ~N \le 10^4~ ~O(N^2)~
Voi moi diem dau, cong dan den khi tong >= K. Chay rieng: dung 16/20 test.
Sub 2: Hai con tro, ~N \le 10^6~ ~O(N)~
Cua so truot: khi tong >= K thi thu hep tu trai. Chay rieng: dung 20/20 test.
Chương trình hoàn chỉnh
Neu N <= 10^4 dung sub 1, nguoc lai dung sub 2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long K;
vector<long long> A;
// Sub 1: vet can O(N^2), dung khi N <= 10^4: voi moi diem dau, cong dan den khi tong >= K
void sub1() {
long long best = LLONG_MAX;
for (int l = 0; l < n; l++) {
long long s = 0;
for (int r = l; r < n; r++) {
s += A[r];
if (s >= K) { best = min(best, (long long)(r - l + 1)); break; }
}
}
cout << (best == LLONG_MAX ? 0 : best) << "\n";
}
// Sub 2: hai con tro O(N): cua so [l..r] co tong >= K thi thu hep tu trai
void sub2() {
long long best = LLONG_MAX, s = 0;
int l = 0;
for (int r = 0; r < n; r++) {
s += A[r];
while (l <= r && s - A[l] >= K) { s -= A[l]; l++; }
if (s >= K) best = min(best, (long long)(r - l + 1));
}
cout << (best == LLONG_MAX ? 0 : 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 (auto& x : A) cin >> x;
if (n <= 10000) sub1();
else sub2();
return 0;
}
Bình luận