Hướng dẫn giải của [TKNP] SQUIRR2
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 cây i rụng quả đầu tiên lúc Ti, sau đó cứ Pi giây rụng thêm một quả. Đến thời điểm t, cây i đã rụng \lfloor (t - Ti) / Pi \rfloor + 1 quả (nếu t \ge T_i, còn không thì 0). Các chú sóc đứng ở N gốc cây, nên tổng số quả thu được là tổng của N cây đã chọn. Để thu được nhiều quả nhất tại thời điểm t, chọn N cây có số quả lớn nhất.
Nhận xét: hàm "tại thời điểm t có đủ K quả" là đơn điệu (t càng lớn thì số quả càng nhiều), nên có thể tìm thời điểm sớm nhất bằng cách thử từng t hoặc tìm nhị phân.
Sub 1: Vét cạn theo thời gian — ~O(T \cdot M)~, dùng khi M \le 1000 và K \le 1000
Thử lần lượt t = 0, 1, 2, ...; với mỗi t đếm số quả của mọi cây, lấy N cây lớn nhất, dừng ở t đầu tiên có tổng đủ K. Nếu chỉ nộp sub này: đúng 8/20 test (12 test còn lại có đáp án lớn, chạy quá giờ).
Sub 2 (đầy đủ): Tìm nhị phân trên thời gian — ~O(\log(100K) \cdot M \log M)~
Đáp án không vượt quá 100 + 100 \cdot K (chỉ cần một cây có P \le 100 rụng đủ K quả). Tìm nhị phân t nhỏ nhất thỏa điều kiện; mỗi lần kiểm tra đếm quả từng cây và dùng nth_element để lấy N cây lớn nhất.
Bẫy: đáp án có thể tới khoảng 10^{11}, và tổng số quả có thể vượt 2 \cdot 10^9, 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 M, N, K và các mảng T, P. Nếu M \le 1000 và K \le 1000 gọi sub1, ngược lại gọi sub2. 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.
Lưu ý (quy ước): hai chú sóc đứng chung một gốc cũng chỉ hứng được đúng số quả của cây đó (quả chỉ có một), nên không có lợi; vì vậy mỗi chú sóc đứng một gốc cây khác nhau, khi ~N \ge M~ thì dùng hết ~M~ cây. Cách hiểu này khớp ví dụ và cả 20 test.
#include <bits/stdc++.h>
using namespace std;
int M, N;
long long K;
vector<long long> T, P; // T[i]: giay dau tien cay i rung qua; P[i]: chu ky rung
// So qua cay i rung trong khoang thoi gian [0, t].
long long countTree(int i, long long t) {
if (t < T[i]) return 0;
return (t - T[i]) / P[i] + 1;
}
// Kiem tra thoi gian t co du K qua hay khong: N chu soc dung o N cay khac nhau,
// lay N cay co nhieu qua nhat, tong phai >= K.
bool enough(long long t) {
vector<long long> c(M);
for (int i = 0; i < M; i++) c[i] = countTree(i, t);
if (N >= M) {
long long s = 0;
for (long long x : c) s += x;
return s >= K;
}
nth_element(c.begin(), c.begin() + N - 1, c.end(), greater<long long>());
long long s = 0;
for (int i = 0; i < N; i++) s += c[i];
return s >= K;
}
// Sub 1: vet can - thu lan luot t = 0, 1, 2, ... cho den khi du K qua. Dung khi M <= 1000 va K <= 1000.
void sub1() {
long long t = 0;
while (!enough(t)) t++;
cout << t << "\n";
}
// Sub 2: day du - tim nhi phan thoi gian t. Cau tra loi <= 100 + 100*K.
void sub2() {
long long lo = 0, hi = 100 + 100 * K;
while (lo < hi) {
long long mid = (lo + hi) / 2;
if (enough(mid)) hi = mid;
else lo = mid + 1;
}
cout << lo << "\n";
}
int main() {
freopen("squirr2.in", "r", stdin);
freopen("squirr2.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> M >> N >> K;
T.resize(M);
P.resize(M);
for (int i = 0; i < M; i++) cin >> T[i];
for (int i = 0; i < M; i++) cin >> P[i];
if (M <= 1000 && K <= 1000) sub1(); // du lieu nho: vet can theo thoi gian
else sub2();
return 0;
}
Bình luận