Hướng dẫn giải của [200 đề thầy Đức] Bài 176: Bí kíp luyện rồng
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Hiccup đánh các con rồng và mỗi lần thắng thì sức mạnh tăng thêm ~y_i~. In YES nếu thắng hết; ngược lại in NO và số rồng còn lại.
Sub 1: Lặp đến khi dừng — ~O(n^2)~, dùng khi ~n \le 100~
Lặp lại: duyệt các con rồng, con nào Hiccup mạnh hơn thì đánh và cộng thêm ~y_i~. Dừng khi một vòng không đánh thêm được con nào. Nếu chỉ nộp sub này: đúng 20/20 test.
Sub 2: Đánh theo sức mạnh tăng dần — ~O(n \log n)~
Sức mạnh của Hiccup chỉ tăng khi thắng, nên luôn đánh con có ~x_i~ nhỏ nhất trước. Sắp xếp theo ~x_i~ tăng dần rồi duyệt. Gặp con không đánh được thì dừng, vì các con sau có ~x_i~ lớn hơn và sức mạnh không đổi. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc ~s~, ~n~ và các cặp ~(x_i, y_i)~. Nếu ~n \le 100~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long s; // sức mạnh ban đầu của Hiccup
long long x[1005], y[1005]; // sức mạnh rồng và mức tăng
// Sub 1: vét cạn O(n^2). Lặp lại: con rồng nào đánh được thì đánh, cho đến khi không đánh thêm được.
void sub1() {
vector<bool> dead(n + 1, false);
int cnt = 0;
long long cur = s;
bool changed = true;
while (changed) {
changed = false;
for (int i = 1; i <= n; i++)
if (!dead[i] && cur > x[i]) {
dead[i] = true;
cur += y[i];
cnt++;
changed = true;
}
}
if (cnt == n) printf("YES\n");
else printf("NO\n%d\n", n - cnt);
}
// Sub 2: O(n log n). Đánh con rồng yếu nhất trước là tối ưu: sức mạnh chỉ tăng,
// nên sắp theo x tăng dần; gặp con không đánh được thì các con sau (x lớn hơn) cũng không đánh được.
void sub2() {
vector<pair<long long, long long>> d;
for (int i = 1; i <= n; i++) d.push_back({x[i], y[i]});
sort(d.begin(), d.end());
long long cur = s;
int cnt = 0;
for (auto &p : d) {
if (cur > p.first) {
cur += p.second;
cnt++;
} else {
break;
}
}
if (cnt == n) printf("YES\n");
else printf("NO\n%d\n", n - cnt);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s >> n;
for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
if (n <= 100) sub1(); // dữ liệu nhỏ: vét cạn
else sub2();
return 0;
}
Bình luận