Hướng dẫn giải của [200 đề thầy Đức] Bài 81: Hecquyn đánh rồng
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
Rồng có ~x~ đầu. Mỗi đòn ~i~ chặt được ~\min(d_i, cur)~ đầu, nếu còn ít nhất 1 đầu thì mọc thêm ~h_i~ đầu. Tìm số đòn ít nhất để hạ rồng, hoặc -1 nếu không thể.
Sub 1: BFS theo số đầu — ~O(C \cdot n)~, dùng khi ~x \le 100, n \le 10~
BFS trên số đầu hiện tại trong đoạn ~[1, 10000]~. Từ số đầu ~cur~, nếu có đòn với ~d_i \ge cur~ thì rồng chết ngay; ngược lại sang trạng thái ~cur - d_i + h_i~. BFS duyệt theo số đòn tăng dần nên đáp án đầu tiên tìm được là nhỏ nhất.
Nếu chỉ nộp sub này: đúng 1/21 test.
Sub 2: Công thức tham lam — ~O(n)~, dùng khi mọi trường hợp còn lại
Gọi ~D = \max d_i~. Nếu ~D \ge x~ thì chỉ cần 1 đòn. Nếu không, mỗi đòn chưa kết thúc giảm số đầu nhiều nhất là ~best = \max(d_i - h_i)~. Nếu ~best \le 0~ thì không bao giờ xuống được nên đáp án -1. Ngược lại cần ~\lceil (x - D)/best \rceil~ đòn giảm, rồi thêm một đòn cuối với ~d = D~.
Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Chương trình đọc ~T~ rồi từng bộ. Nếu ~x \le 100~ và ~n \le 10~ thì gọi sub1, ngược lại gọi sub2. Ví dụ: ~x = 10~ với ~D = 8~, ~best = 6~ cho 2 đòn. Dùng số nguyên 64 bit.
#include <bits/stdc++.h>
using namespace std;
int n;
long long x; // so dau ban dau cua rong
vector<long long> d, h; // don thu i: chat d[i] dau, roi rong moc them h[i] dau
// Sub 1: vet can. BFS theo so dau hien tai cur (gioi han cur <= 10000), moi buoc la mot don.
// Neu co don nao co d[i] >= cur thi chac chan thang o buoc nay. BFS duyet theo so don
// tang dan nen dap an dau tien tim duoc la nho nhat. Dung khi x <= 100, n <= 10.
void sub1() {
const int CAP = 10000;
vector<int> dist(CAP + 1, -1);
queue<long long> q;
dist[x] = 0;
q.push(x);
while (!q.empty()) {
long long cur = q.front();
q.pop();
for (int i = 0; i < n; i++)
if (d[i] >= cur) {
cout << dist[cur] + 1 << "\n";
return;
}
for (int i = 0; i < n; i++) {
long long nx = cur - d[i] + h[i]; // cur > d[i] nen nx >= 1
if (nx <= CAP && dist[nx] == -1) {
dist[nx] = dist[cur] + 1;
q.push(nx);
}
}
}
cout << -1 << "\n";
}
// Sub 2: cong thuc.
// D = max d[i]. Neu D >= x thi 1 don la du.
// Neu khong, moi don chua ket thuc chi giam so dau nhieu nhat best = max(d[i] - h[i]).
// Can dua so dau xuong <= D truoc don cuoi, nen so don truoc = ceil((x - D) / best).
// Neu best <= 0 thi khong bao gio xuong duoc, dap an -1.
void sub2() {
long long D = 0, best = LLONG_MIN;
for (int i = 0; i < n; i++) {
D = max(D, d[i]);
best = max(best, d[i] - h[i]);
}
if (D >= x) {
cout << 1 << "\n";
return;
}
if (best <= 0) {
cout << -1 << "\n";
return;
}
long long k = (x - D + best - 1) / best;
cout << k + 1 << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> n >> x;
d.assign(n, 0);
h.assign(n, 0);
for (int i = 0; i < n; i++) cin >> d[i] >> h[i];
if (x <= 100 && n <= 10) sub1();
else sub2();
}
return 0;
}
Bình luận