Hướng dẫn giải của Đủ chất (KS3)
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
Mỗi sáng cần 2 chiếc bánh mì, bánh chỉ giữ được k ngày kể từ ngày mua. Ta chọn ngày mua sao cho tổng chi phí nhỏ nhất. Một chiếc mua ở ngày j phục vụ được các ngày i với j ≤ i ≤ j + k - 1, nên ngày i sẽ mua ở ngày rẻ nhất trong cửa sổ [i - k + 1, i].
Sub 1: k = 1, mua đúng ngày ăn — ~O(n)~
Khi k = 1 bánh không để dành được, mỗi ngày phải mua đúng 2 chiếc với giá ngày đó. Đáp án là 2 · tổng c_i. Nếu chỉ nộp sub này: đúng 4/20 test.
Sub 2: Vét cạn trên cửa sổ — ~O(n \cdot k)~, dùng khi ~n \le 1000~ và ~k \le 1000~
Với mỗi ngày i, duyệt các ngày j trong [i - k + 1, i], lấy giá nhỏ nhất rồi nhân 2 cộng vào đáp án. Nếu chỉ nộp sub này: đúng 18/20 test (2 test còn lại quá giờ vì n, k lớn hơn miền của sub).
Sub 3: Cửa sổ trượt bằng deque đơn điệu — ~O(n)~
Duy trì một deque chứa các chỉ số ngày có giá tăng dần. Khi thêm ngày i, bỏ đuôi có giá lớn hơn hoặc bằng c_i (chúng không bao giờ là min nữa vì i đến sau và sống lâu hơn). Bỏ đầu deque khi chỉ số đã nằm ngoài cửa sổ [i - k + 1, i]. Đầu deque luôn là ngày rẻ nhất trong cửa sổ.
Bẫy: đáp án có thể lên tới 2 · 10^5 · 10^5 = 2 · 10^10, nên phải dùng long long.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu. Nếu k = 1 gọi sub1. Nếu n và k đều không quá 1000 gọi sub2. Các trường hợp còn lại gọi sub3. Khi đi thi, nộp đúng chương trình này: sub nhỏ ăn điểm chắc chắn, sub lớn chạy nhanh cho dữ liệu lớn.
#include <bits/stdc++.h>
using namespace std;
int n, k;
long long c[100005]; // gia banh ngay i
// Sub 1: k = 1, moi ngay mua dung so banh can an (2 cai) voi gia ngay do. O(n)
void sub1() {
long long ans = 0;
for (int i = 1; i <= n; i++) ans += 2LL * c[i];
cout << ans << "\n";
}
// Sub 2: vet can. Moi ngay i can 2 cai, co the mua o bat ky ngay j trong [i-k+1, i]
// (banh mua ngay j giu duoc den ngay j+k-1). Voi moi i, tim gia re nhat trong cua so do. O(n*k)
void sub2() {
long long ans = 0;
for (int i = 1; i <= n; i++) {
long long best = LLONG_MAX;
for (int j = max(1, i - k + 1); j <= i; j++) best = min(best, c[j]);
ans += 2LL * best;
}
cout << ans << "\n";
}
// Sub 3: dung deque don dieu de lay min cua cua so truot. O(n)
void sub3() {
deque<int> dq; // chi so ngay, gia tang dan trong deque
long long ans = 0;
for (int i = 1; i <= n; i++) {
while (!dq.empty() && c[dq.back()] >= c[i]) dq.pop_back();
dq.push_back(i);
while (dq.front() < i - k + 1) dq.pop_front(); // bo ngay ngoai cua so
ans += 2LL * c[dq.front()];
}
cout << ans << "\n";
}
int main() {
freopen("FOOD.INP", "r", stdin);
freopen("FOOD.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> c[i];
if (k == 1) sub1();
else if (n <= 1000 && k <= 1000) sub2();
else sub3();
return 0;
}
Bình luận