Hướng dẫn giải của [VTT Q4 Contest 12] Bài 4: Kiểm tra bài cũ [CHECK]
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ý đọc các khổ theo thứ tự 1, 2, 3, ... và được bỏ qua tối đa ~k~ khổ. Nếu đọc đến khổ thứ ~p~ và đã bỏ ~j~ khổ thì số khổ đọc được là ~p - j~, với tổng thời gian đã đọc không vượt quá ~s~. Với mỗi tiền tố, nếu phải bỏ thì nên bỏ những khổ lâu nhất.
Sub 1: ~k = 0~ — ~O(n)~
Không được bỏ khổ nào: cộng dồn thời gian cho đến khi vượt ~s~, số khổ đọc trước đó là đáp án. Nếu chỉ nộp sub này: đúng 10/20 test (các test có ~k = 0~).
Sub 2: ~k = 1~ — ~O(n)~
Với mỗi tiền tố độ dài ~p~, nếu tổng không quá ~s~ thì đọc được ~p~ khổ; nếu quá nhưng tổng trừ khổ lớn nhất của tiền tố không quá ~s~ thì đọc được ~p - 1~ khổ. Chỉ cần duy trì tổng và giá trị lớn nhất. Nếu chỉ nộp sub này: đúng 16/20 test.
Sub 3: ~k~ bất kỳ — ~O(n \cdot k)~
Giữ danh sách ~k~ khổ lớn nhất của tiền tố hiện tại (sắp giảm dần, chèn kiểu sắp xếp chèn trong ~O(k)~). Với mỗi tiền tố, thử ~j = 0, 1, 2, \dots~ khổ bị bỏ (là ~j~ khổ lớn nhất) và dừng ở ~j~ nhỏ nhất làm tổng không vượt ~s~; khi đó đọc được ~p - j~ khổ. Lấy giá trị lớn nhất trên mọi tiền tố, tổng cộng khoảng ~10^7~ phép tính. 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 rồi chọn sub theo ~k~ (0, 1 hoặc lớn hơn). Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n, k;
long long s;
int t[100005];
// Sub 1 (k = 0): không được bỏ khổ nào, đọc lần lượt cho đến khi hết thời gian
void sub1() {
long long sum = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
sum += t[i];
if (sum > s) break;
ans = i + 1;
}
printf("%d\n", ans);
}
// Sub 2 (k = 1): với mỗi tiền tố, nếu quá giờ thì bỏ khổ lâu nhất
void sub2() {
long long sum = 0;
int mx = 0, ans = 0;
for (int i = 0; i < n; i++) {
sum += t[i];
mx = max(mx, t[i]);
if (sum <= s) ans = max(ans, i + 1);
else if (k >= 1 && sum - mx <= s) ans = max(ans, i); // i + 1 khổ, bỏ 1
}
printf("%d\n", ans);
}
// Sub 3: giữ danh sách k khổ lớn nhất của tiền tố (đã sắp giảm dần).
// Với tiền tố độ dài p, bỏ j khổ lớn nhất (j nhỏ nhất để vừa thời gian) thì đọc được p - j khổ.
void sub3() {
vector<int> top; // giảm dần, kích thước <= k
long long sum = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
sum += t[i];
// chèn t[i] vào top
int pos = top.size();
top.push_back(t[i]);
while (pos > 0 && top[pos - 1] < top[pos]) { swap(top[pos - 1], top[pos]); pos--; }
if ((int)top.size() > k) top.pop_back();
long long cur = sum;
for (int j = 0; j <= (int)top.size(); j++) {
if (j > 0) cur -= top[j - 1];
if (cur <= s) { ans = max(ans, i + 1 - j); break; }
}
}
printf("%d\n", ans);
}
int main() {
freopen("CHECK.INP", "r", stdin);
freopen("CHECK.OUT", "w", stdout);
scanf("%d %lld %d", &n, &s, &k);
for (int i = 0; i < n; i++) scanf("%d", &t[i]);
if (k == 0) sub1();
else if (k == 1) sub2();
else sub3();
}
Bình luận