Hướng dẫn giải của Kiểm tra bài cũ (KS THCS 05)
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
Nếu Tý đọc đến khổ ~p~ và bỏ qua ~j~ khổ (~j \le k~) thì tổng thời gian đọc là tổng ~t_1..t_p~ trừ tổng ~j~ khổ lớn nhất trong ~1..p~, số khổ đọc được là ~p - j~. Với mỗi ~p~ chọn ~j~ nhỏ nhất sao cho tổng thời gian không vượt ~s~. Quy ước: Tý đọc theo thứ tự, các khổ đọc được là một tiền tố đã bỏ đi tối đa ~k~ khổ (bỏ khổ nào cũng được, nên bỏ các khổ dài nhất); đáp án là ~p - j~ lớn nhất.
Sub 1: Thử mọi p — ~O(n^2 \log n)~, dùng khi ~n \le 1000~
Với mỗi ~p~, sắp xếp các khổ ~1..p~ giảm dần rồi thử ~j~ từ ~0~ đến ~k~. Nếu chỉ nộp sub này: đúng 9/20 test.
Sub 2: Hàng đợi ưu tiên — ~O(n \cdot k \log k)~
Giữ một min-heap gồm ~k~ khổ lớn nhất của tiền tố ~1..p~ (đủ cho mọi ~j \le k~), rồi làm như sub 1 trên ~k~ phần tử đó. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Nếu ~n \le 1000~ dùng sub 1, còn lại dùng sub 2. 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;
vector<long long> t; // t[1..n]: thoi gian doc khổ thu i
// Y tuong: neu doc den khổ p (doc theo thu tu) va bo qua j khổ thi tong thoi gian doc
// la (tong t[1..p]) - (tong j khổ dai nhat trong 1..p). Voi moi p, chon j nho nhat thoa
// dieu kien <= s; so khổ doc duoc = p - j.
// Sub 1: voi moi p, sap xep lai khổ 1..p roi thu moi j. O(n^2 log n) — dung khi n <= 1000
void sub1() {
long long ans = 0;
for (int p = 1; p <= n; p++) {
vector<long long> v(t.begin() + 1, t.begin() + p + 1);
sort(v.rbegin(), v.rend()); // giam dan
long long total = 0;
for (long long x : v) total += x;
long long top = 0;
for (int j = 0; j <= min(k, p); j++) {
if (j > 0) top += v[j - 1];
if (total - top <= s) { ans = max(ans, (long long)(p - j)); break; }
}
}
cout << ans << "\n";
}
// Sub 2: giu hang doi uu tien (min-heap) gom k khổ lon nhat cua tien to 1..p, O(n * k log k)
void sub2() {
priority_queue<long long, vector<long long>, greater<long long>> pq;
long long total = 0, ans = 0;
for (int p = 1; p <= n; p++) {
total += t[p];
pq.push(t[p]);
if ((int)pq.size() > k) pq.pop();
priority_queue<long long, vector<long long>, greater<long long>> q2 = pq;
vector<long long> v;
while (!q2.empty()) { v.push_back(q2.top()); q2.pop(); }
sort(v.rbegin(), v.rend());
long long top = 0;
for (int j = 0; j <= min(k, p); j++) {
if (j > 0) top += v[j - 1];
if (total - top <= s) { ans = max(ans, (long long)(p - j)); break; }
}
}
cout << ans << "\n";
}
int main() {
freopen("CHECK.INP", "r", stdin);
freopen("CHECK.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> s >> k;
t.assign(n + 1, 0);
for (int i = 1; i <= n; i++) cin >> t[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận