Hướng dẫn giải của [KSCUM VT] CÂU 2
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 đoạn ngày liên tiếp ngắn nhất có tổng số kg cá ít nhất là X. Vì mỗi A_i >= 1 nên tổng tăng khi mở rộng đoạn, và có thể dùng hai con trỏ. Nếu không có đoạn nào đủ X thì in 0.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 10^4~
Với mỗi ngày bắt đầu i, cộng dần A_j cho đến khi tổng đạt X. Ghi lại độ dài j - i + 1 rồi chuyển sang i tiếp theo, vì các j lớn hơn chỉ cho đoạn dài hơn. Nếu chỉ nộp sub này: đúng 16/20 test.
Sub 2: Hai con trỏ — ~O(n)~
Giữ cửa sổ [l, r]. Mở rộng r, sau đó co l khi bỏ được ngày đầu mà tổng vẫn đạt X. Bẫy: tổng có thể lên tới 10^15, nên dùng kiểu long long. Nếu đề không có đoạn nào thỏa mãn thì kết quả là 0. Sub 2 đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu rồi gọi sub 1 khi n \le 10^4, còn lại gọi sub 2. Khi đi thi nên viết như vậy: nếu sub 2 sai thì sub 1 vẫn ăn điểm các test nhỏ.
#include <bits/stdc++.h>
using namespace std;
int n;
long long X;
long long a[1000005]; // a[1..n]: số kg cá dự báo của từng ngày
// Sub 1: vét cạn O(n^2) — với mỗi ngày bắt đầu i, cộng dần cho đến khi đủ X kg
void sub1() {
int best = 0; // 0 = chưa tìm được đoạn nào
for (int i = 1; i <= n; i++) {
long long s = 0;
for (int j = i; j <= n; j++) {
s += a[j];
if (s >= X) {
int len = j - i + 1;
if (best == 0 || len < best) best = len;
break; // các j sau chỉ cho đoạn dài hơn
}
}
}
cout << best << "\n";
}
// Sub 2: hai con trỏ O(n) — A_i > 0 nên tổng tăng khi mở rộng, co đoạn từ trái khi vẫn đủ X
void sub2() {
int best = 0;
long long s = 0;
int l = 1;
for (int r = 1; r <= n; r++) {
s += a[r];
while (l < r && s - a[l] >= X) { // bỏ ngày đầu nếu đoạn vẫn đủ X
s -= a[l];
l++;
}
if (s >= X) {
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 >> X;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 10000) sub1(); // dữ liệu nhỏ: vét cạn cho chắc
else sub2();
return 0;
}
Bình luận